- 고정 크기의 배열(Array) 등에 의해 구현된 선형 리스트의 단점을 보완한 자료구조
- 동적으로 크기가 변할 수 있고,
- 삭제, 삽입 시 데이터 이동의 필요가 없다.
- 데이터 및 링크(포인터)에 의해 비연속적, 비순차적으로 연결된 선형 자료구조
- 노드 (Node) : 연결 리스트 내 각각의 원소, 데이터와 포인터를 갖는다.
- 데이터 필드 : 저장하고자 하는 데이터 (정수나 구조체 등) 가 들어간다.
- 포인터 필드 : 다른 노드를 가리키는 포인터가 저장되고 이를 이용하여 다른 노드에 접근할 수 있다.
- 노드는 자기 참조 구조체를 이용하여 정의한다.
- 자기 참조 구조체 : 자신과 동일한 구조체에 대한 포인터(다음 노드의 주소를 저장하는 링크 필드)를 멤버로 가진다.
struct node {
int data; // 데이터 필드
struct node *next; // 링크 필드 : 다음 노드의 주소 저장 (포인터)
}
typedef struct node Node;
Node *head = NULL; // 첫 번째 노드의 주소를 저장할 포인터 - head는 Node 타입의 포인터이다.-
포인터로 연결
- 원소들이 메모리 내 어느 위치에도 가능
- 동적으로 노드의 삽입과 삭제가 용이하다. (항목의 삭제, 삽입 시 데이터 이동 필요 없음)
- 전체 데이터를 이동할 필요없이 포인터만 변경해 주면 간단히 구현할 수 있다.
- 원소 끝 포인터는 null을 지시한다.
-
크기가 가변적임
- 메모리가 허용하는 만큼 커질 수 있다.
- 메모리 공간 사용이 효율적이지만, 포인터를 위해 추가 메모리가 필요하다.
-
원소의 순서 유지 및 순차 접근
- 원소의 순서는 링크를 이용해 유지시킨다.
- 원소에 검색, 삭제 및 추가를 할 때 첫번째 원소부터 순차적으로 따라간다.
-
다른 자료구조(추상 자료형, ADT: Abstract Data Type)의 기반이 된다.
- 큐, 스택, 해시 테이블 등
| 배열 | 연결리스트 | 설명 | |
|---|---|---|---|
| 구현 방법 | 배열로 선언 예) int list[N];
|
연결 리스트 예) list_ptr ptr;
|
|
| 기억 장소 확보 시점 |
프로그램 수행 전 (compile time) 정적 기억 장소 할당 (기억 장소 N개로 시작) |
프로그램 수행 후 (run time) 동적 기억 장소 할당 (기억 장소 1개로 시작) |
배열에서 기억 장소가 수행 전에 할당되는 경우 기억 장소 크기가 고정되고, 사용 여부에 관계 없이 기억 장소를 확보한다. |
| 기억 장소 연속성 |
연속된 기억 장소 할당 | 기억 장소 힙(heap) 영역에서 임의로 할당 |
연결리스트에서는 기억 장소가 여기저기 흩어져 있고 링크를 통해 연결이 된다. |
| 탐색 시간 복잡도 |
|||
| 삽입/삭제 시간 복잡도 |
int main() {
// 첫번째 노드 추가 & head에 연결
head = (Node *)malloc(sizeof(Node)); // 동적 메모리 할당
head->data = "Tuesday"; // head가 첫번째 노드를 가리킴
head->next = NULL;
// 두번째 노드 추가 & 첫번째 노드에 연결
Node *q = (Node *)malloc(sizeof(Node));
q->data = "Thursday";
q->next = NULL;
head->next = q;
// Tuesday 노드 앞에 Monday 노드 연결(새로운 첫번째 노드)
q = (Node *)malloc(sizeof(Node));
q->data = "Monday";
q->next = head;
head = q;
// 세 개의 노드를 순서대로 출력하기
Node *p = head;
while (p!=NULL) {
printf("%s\n", p->data); //p가 현재 가리키고있는 노드를 출력한다.
p = p->next; //p가 다음 노드를 가리키도록 한다. (next에는 다음 노드의 주소가 담겨있음)
// 다음 노드가 없다면, p==NULL이 되기 때문에 반복문이 종료된다 */
}
return 0;
}#Node 정의
class Node:
def __init__(self, data, next=None): #data 만 입력시 next 초기값은 None이다.
self.data = data #다음 데이터 주소 초기값 = None
self.next = next
#Node1 생성해보기
node1 = Node(1)
head = node1
#Node2 생성해보기
node2 = Node(3)
node1.next = node2- 삽입
- 삭제
- 단순 연결 리스트 (Singly Linked Linear List): 노드들을 한 줄로 연결시킨 자료 구조
- 각 노드 마다, 값(데이터) 및 다음 링크(포인터)를 갖음
- 단방향 연결됨 : 각 원소(노드)에 단방향 단일 링크(포인터) 필드 필요
- 노드 링크는, 다음 노드를 가리킴
- 마지막 노드의 링크는, NULL 값을 갖음
- 이중 연결 리스트 (Doubly Linked Linear List)
- 양방향 가능 : 후행 노드 및 선행 노드 모드를 가리킬 수 있도록 매 노드마다 2개의 링크(포인터)를 가짐
- 즉, 순방향, 양방향 모두 탐색 가능
- 원형 연결 리스트 (Circularly Linked Linear List)
- 마지막 노드의 링크가 리스트의 처음 노드를 가리킴
- 즉, 단순 연결 리스트의 처음과 끝을 연결하면 원형 연결 리스트가 됨
- 파이썬의 리스트는 연결리스트가 아니다.
- 연결리스트는 임의의 위치에 원소를 삽입하거나 삭제할 때 빠르게 수행한다는 장점이 있다. 하지만 기억 영역(메모리)와 속도 면에서는 배열보다 효율이 뒤떨어진다.
- 파이썬의 리스트는 모든 원소를 연속으로 메모리에 배치하는 '배열'로 내부에서 구현하고 있다. 따라서 속도가 급격히 떨어지지 않는다.
- 또한 원소를 하나씩 추가, 삽입할 때마다 내부에서 메모리를 확보하거나 해제하지 않는다. 실제 필요한 메모리보다 여유있게 미리 마련해놓기 때문이다.