[자료구조] 연결 리스트 (Linked list)

자료구조의 연결리스트는 배열과 비슷하면서도 다른 구조를 보여준다.
연결리스트에 대해 알아보자.

 

연결 리스트

연결 리스트는 배열의 삽입 및 삭제에 발생하는 비용이나 정적 크기 등의 단점을 보완하기 위해 만들어졌다.

정보는 하나의 노드에 저장되고, 그 노드에는 데이터와 다음 노드에 대한 정보를 담은 포인터가 저장된다.

종류에는 단일 연결 리스트(Singly linked linear list), 이중 연결 리스트(Doubly linked linear list), 원형 연결 리스트(Circularly linked linear list)가 있다.

---

각 연결 리스트의 구분

- 단일 연결 리스트(Singly linked linear list)

 

각 노드에 데이터와 한 개의 포인터 공간이 존재하고, 각 포인터는 다음 노드를 가리킨다.

 

 

- 이중 연결 리스트(Doubly linked linear list)

 

각 노드에 데이터와 두 개의 포인터 공간이 존재하고, 각각의 포인터는 앞과 뒤의 연결된 노드를 가리킨다.

 

 

- 원형 연결 리스트(Circularly linked linear list)

 

단일 연결 리스트와 비슷하지만, 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

---

특징

1. 새로운 요소가 추가될 때마다 메모리를 할당하는 동적 메모리 할당을 사용한다.
2. 요소에 접근할 때 연결되어 있는 구조이기 때문에 첫 노드부터 확인하는 순차 접근만 가능하다.
3. 다음 노드와 연결하기 위한 포인터로 인해 추가 저장공간이 필요하다.

---

시간복잡도

1. 읽기(read) : 각 요소에 대해 인덱스를 통해서 바로 접근할 수 있기 때문에 O(1)의 시간 복잡도를 가진다.
2. 삽입(insert) 및 삭제(delete) : 동적 메모리 할당이므로 동적인 크기를 가진다.
   시작 위치에 넣는 경우라면 O(1), 중간 위치라면 탐색 후 삽입/삭제이므로 중간 위치 탐색시간 + O(1), 마지막 위치일 때 크기를 안다고 하면 O(1), 모른다면 O(n)이다.
3. 검색(search) : 처음부터 원하는 요소가 어디있는지 탐색해야 한다. 그러므로 O(n)의 시간 복잡도가 발생한다.

---

장점

1. 크기를 동적으로 설정할 수 있다.
2. 삽입 및 삭제에 많이 비용이 발생하지 않고 간단하다.

단점

1. 원하는 위치에 바로 접근을 할 수 없다.
2. 포인터를 넣을 추가 공간이 필요하다.

 

---

사진출처

연결리스트의 구분