연결 리스트

연결 리스트(linked representation): 동적으로 크기가 변할 수 있고 삭제나 삽입 시 데이터 이동할 필요 x

- 포인터를 사용하여 데이터들을 연결 

- 다른 자료구조(트리, 그래프, 스택, 큐 등)를 구현할 때도 많이 사용

- 물리적으로 흩어져 있는 자료들을 포인터로 서로 연결하여 하나로 묶음

- 중간에 삭제하거나 삽입할 때 앞뒤에 있는 데이터들을 이동할 필요 없이 포인터만 수정

 

- 하나의 프로그램 내에 동시에 여러 개의 연결 리스트 존재 가능

- 이 경우 첫 번째 데이터로 연결 리스트들을 구별(첫 번째 데이터를 확보하고 포인터로 따라가면 나머지 데이터들을 얻을 수 있음)

 

- 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어 추가 가능

- 배열로 구현하는 것보다 구현이 어려움

- 데이터와 포인터를 모두 저장하므로 메모리 공간을 많이 사용

- i번째 데이터를 찾으려면 앞에서부터 순차적으로 접근해야 함

---

연결 리스트의 구조

- 연결 리스트는 노드(node)들의 집합

- 노드들은 메모리의 어떤 위치에든 존재할 수 있음

- 다른 노드로 가기 위해서는 현재 노드의 포인터를 이용

노드의 구조

- 노드는 데이터 필드(data field)와 링크 필드(link field)로 구성

- 데이터 필드에는 데이터가 저장

- 링크 필드에는 포인터가 저장

- 헤드 포인터(head pointer): 첫 번째 노드를 가리키는 변수

- 마지막 노드의 링크 필드는 NULL로 설정되어 더 이상 연결된 노드가 없음을 표시

- 필요할 때마다 malloc()을 이용하여 동적으로 노드 생성

---

연결 리스트의 종류

 

단순 연결 리스트(singly linked list)

- 한 방향으로만 연결된 연결 리스트

- 체인(chain)이라고도 함

- 마지막 노드의 링크는 NULL값을 가짐

 

원형 연결 리스트(circular linked list)

- 마지막 노드의 링크가 첫 번째 노드를 가리킴

 

이중 연결 리스트(doubly linked list)

- 각 노드마다 2개의 링크가 존재

- 한 링크는 앞에 있는 노드를 가리키고 다른 링크는 뒤에 있는 노드를 가리킴

위에서부터 단순 연결, 원형 연결, 이중 연결 리스트