연결리스트(linked list)

목 차 링크드 리스트의 개요 링크드 리스트의 종류

링크드 리스트의 개요 일정한 순서를 가지는 데이터 요소들을 표현하는 방법 중의 하 나이다. 배열과 다르게 데이터 요소들의 논리적인 순서만 유지되고 기 억 장소 내에서는 각 데이터 요소들은 논리적인 순서와는 상관없는 임의의 위치 를 가지도록 하는 자료 구조이다. 연결리스트에서는 각 데이터 요소들이 기억 장소 내의 어떤 위 치에 어떤 항목이 있는지를 표시해 주어야 한다. 이를 위해 데이터 요소에는 데이 터 값, 위치 정보 도 저장해 주어야 한다. 즉, 배열에서의 단점을 제거하면서 메모리를 효율적으로 사용 하고 삽입과 삭제 가 쉬워 처리 시간이 단축되나, 관리 유지에 부가적 비용이 든다.

링크드 리스트의 개요(계속) head->next->next->data B C D 256 300 128 400 NULL head head->next head->next->next->next head->next->next head->data head->next-> data head->next->next->data < 연결리스트의 구조>

링크드 리스트의 개요(계속) 예 struct person{ char name[20]; struct person *next; }; struct person *new; struct person *head; head = NULL; new = (person *)malloc(sizeof(struct person)); new->next = head; head = new;

head->next-> data head->next->next 링크드 리스트의 개요(계속) A B C D 256 300 128 400 NULL head head->next head->data head->next-> data head->next->next <삭제>

링크드 리스트의 개요(계속) 삽입 예 person *marker; new = (LINK)malloc(sizeof(person)); new->next = marker->next; marker->next = new;

링크드 리스트의 개요(계속) F head->next->next head->next-?next-> data B C D 256 300 128 400 NULL head head->next head->next->next->next->next head->next->next head->data head->next-> data head->next->next->next->data <삽입> F head->next-?next-> data head->next->next->next

링크드 리스트의 개요(계속) 삭제 (예) person *current1, *current2; current1 = head; current2 = current1->next; while(current2->next != NULL) { current1 = current2; } free(current1->next); current1->next = null; if(head == current1) head = null;

링크드 리스트의 종류 단일 연결리스트(singly linked list) 포인터를 이용해서 한 쪽방향으로만 연결되어 있는 구조 환형 연결리스트(circular linked list) 환형큐와 마찬가지로 마지막 노드에서 처음 노드로 연결하여 원형으로 된 구조 이중 연결리스트(doubly linked list) 한 쪽방향으로만 연결 된 경우 반대 방향의 노드를 접근하기 어렵다는 단점을 보안, 양방향으로 포인터를 이용해서 연결한 구조

링크드 리스트의 종류(계속) 구조가 간단하고, 기억 장소의 소모가 적은 반면에 역방향으로 리스트를 검색할 수 없음 구조가 간단하고, 기억 장소의 소모가 적은 반면에 역방향으로 리스트를 검색할 수 없음 -> 노드를 삽입하거나 삭제하려면 별도의 포인터가 필요 위 단점을 해결하기 위해 이중 연결리스트(doubly linlked list)를 사용

링크드 리스트의 종류(계속) - 이중 연결리스트의 구조 노드가 양쪽 방향으로 연결되어 있는 리스트 이중 연결리스트의 구조 오른쪽 방향 : rlink(선행 노드) 왼쪽 방향 : llink(후행 노드) llink data rlink 이중연결리스트의 노드 구조

링크드 리스트의 종류(계속) 이중 연결리스트의 장단점 단일 연결리스트는 오직 하나의 연결 부분(링크필드)을 가지고 있지만, 이중연결 리스트는 연결부분을 두개로 하여 한 개일 때 보다는 기억장소의 낭비가 있지만 효율적인 리스트 운영이 가능

링크드 리스트의 종류(계속) 이중 연결리스트의 동작 노드삽입 노드삭제 head NULL NULL X head A B C D NULL NULL <이중연결리스트의 노드 삽입> head A B C D NULL NULL <이중연결리스트의 노드 삭제>

링크드 리스트의 종류(계속) - 환형 연결리스트 (circular Linked List) 맨 마지막 노드의 포인터를 NULL로 하는 대신에 맨 앞의 노드에 연결시켜서 원형구조를 만든것. 환영 연결리스트의 구조 head A B C D <환형연결리스트의 구조>