puretension

이중 원형 연결 리스트 원형 이중 연결 리스트란 각 노드가 두 개의 포인터를 가지며, next 포인터는 리스트에서 다음 노드를 가리키고, prev 포인터는 리스트에서 이전 노드를 가리키는 이중 연결리스트를 기반으로 한다. 여기에 추가해서, 마지막 노드의 next 포인터가 NULL을 가리키는게 아니라 (head포인터가 가리키는) 첫 번째 노드를 가리키며, 첫 번째 노드의 prev 포인터는 마지막 노드를 가리킴으로써 원형 구조를 만듭니다.(무한 싸이클 느낌ㅋㅋ) 이중 원형 연결 리스트의 장점 1. 노드를 삽입하거나 삭제하는 등의 작업이 리스트의 크기와 관계없이 상수 시간 O(1)으로 수행가능 why? 인접한 노드의 포인터만 업데이트해주면 됨 2. 데이터 정렬(sort) 가능 이중원형 연결리스트는 개인적으로 ..

원형 연결 리스트(CircleLinkedList) : 단일 연결리스트와 거의 동일해 보이지만, 마지막 노드가 NULL이 아닌 첫 번째 노드(head가 가리키는 노드)를 가리킨다 단순 연결리스트와 원형 연결리스트 비교 원형연결리스트의 장점 단순 연결 리스트처럼 머리와 꼬리를 가리키는 포인터 변수(head포인터와 tail포인터)를 각각 두지 않아도, 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드 추가 가능 지금까지의 (더미노드 포함)단일 연결리스트에서는 head 포인터를 통하여 새로운 노드를 추가하는 방식이었음 이번에는 tail포인터만으로 머리와 꼬리 둘다에 노드를 추가해볼 것 꼬리를 가리키는 포인터 변수는 tail 머리를 가리키는 포인터 변수는 tail -> next tail포인터만을 사용하여 머리와..

더미노드란? 유효한 데이터를 지니지 않는 그냥 빈(empty) 노드 처음 추가되는 노드는 무조건 두번째이후의 노드가 되기 때문에 노드를 삽입(추가), 삭제, 조회 할때 일관된 형태로 구성 가능 더미노드의 장점 더미노드를 통해서 삽입/삭제/참조가 이루어지기에, 코드가 간결해진다.(첫번째 노드일 경우와 2번째노드 이후의 경우를 안나눠줘도 됨) 더미노드가 있으면 이중 연결리스트에서 head와 tail이 움직일 필요가 없어진다. 더미노드를 사용하면 위와같은 조건문(if/else)으로, 굳이 case분류를 해주지 않아도 된다 (노드가 0개인가, 1개인가...할 필요 X) Why? 더미노드가 이미 1개가 만들어져 있기 때문 이전 단일 연결리스트와의 차이점 1. Node구조체 포인터들을 하나의 구조체로 묶음 2. 헤..

기존의 배열리스트의 단점 1. 정적인(static) 메모리 구성 배열은 정적인(static) 자료구조로 한번 크기를 정하면 크기 수정이 불가하고 이미 정한 배열 크기 이상의 데이터 개수는 삽입 불가함 2. 배열에 속한 데이터를 삭제하거나, 새로운 데이터 추가시 한칸씩 이동 시켜줘야하는 번거로움 물론 배열리스트와 연결리스트가 시간복잡도면에서 어느 하나가 절대적으로 유리하다고 할 수는 없다. 각각이 지닌 장단점이 다르기 때문이며 둘의 시간복잡도 비교에 대해서는 다른 포스팅을 통해 다루기로 하고 연결리스트에 집중! 연결 리스트(Linked List) 배열 리스트와 달리 메모리의 동적(dynamic)할당을 기반으로 구현된 리스트 연결리스트의 장점 1. 원할때 필요한 만큼 메모리를 동적할당하여 데이터를 생성하여 ..

ArrayList(순차 리스트) - 배열 기반 구현 리스트 LinkedList(연결 리스트) - 메모리의 동적할당 기반 구현 리스트 구현 방법 기준으로 한 구분으로 두 리스트의 ADT는 동일 리스트 자료구조는 데이터를 나란히 저장하고, 중복 데이터의 저장을 허용한다. 배열리스트의 장점과 단점 장점 - index값만 기준으로 해서 데이터 참조가 쉽다 단점 - 배열길이가 초기에 결정되어 변경이 불가능하다. 삭제과정에서 데이터 이동 빈번히 일어난다. //정수만 저장되어 있는 배열리스트 type def LData의 사용 이유 1. int형이라고해서 어느 CPU에서나 4바이트가 아니다. 16비트와 8비트에서의 CPU에선 int가 2바이트, 1바이트로 다르기 때문에 여러 시스템 환경(CPU가 다른)에서도 동일하게 ..

작년에 배운 경험이 있으나, 깊이있게 해보지 않고 겉핥기식으로 각 자료구조의 코드 구현 - 백준으로 PS만 대강해보며 넘겼었다. 곧 개강후 전공으로 C로하는 자료구조가 있기에 이번 기회에 윤성우의 열혈 자료구조 책을 참조해 제대로 다져보고자 한다. (앞으로의 그림 자료들 역시 이 책을 참조하였다) https://search.shopping.naver.com/book/catalog/32441031922 윤성우의 열혈 자료구조 : 네이버 도서 네이버 도서 상세정보를 제공합니다. search.shopping.naver.com 1. 알고리즘 성능 평가요소 1. 시간 복잡도(Time Complexity): 얼마나 빠르게 결과를 출력 하는가?, 연산횟수는 얼마나 되는가? 2. 공간 복잡도(Space Complexi..