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

연결 리스트란?

---

단순 연결 리스트의 구조 ❘ https://ko.wikipedia.org/wiki/연결_리스트

연결 리스트는 노드들로 구성되어 있다. 위 그림에서 각각의 큰 직사각형들이 하나의 노드이다. 노드는 데이터 영역과 링크
(포인터) 영역으로 구성되어 있다. 데이터 영역은 데이터를 저장하는 공간이고 링크 영역은 다음 노드를 가리키는 역할을 한다.

 

연결 리스트의 특징

---

연결리스트의 가장 큰 특징은 데이터를 삽입/삭제할 때, 노드를 추가/삭제하면 되므로 미리 크기를 정의하지 않아도 된다는 것이다. 연결리스트는 필요에 따라 크기를 동적으로 조절할 수 있다. 연결리스트의 다른 특징은 다음과 같다.

• 삽입 및 삭제의 효율성: 데이터의 삭제와 삽입 모두 삽입하는 위치의 전 노드의 포인터 또는 삽입하는 노드의 포인터를 조정하기만 하면 된다. 따라서 시간복잡도는 O(1)로 효율적이다.
• 임의 접근(random access) 불가: 연결 리스트는 인덱스를 활용하지 않으므로 임의 접근이 불가능하다. 첫 노드부터 차례대로 접근해야 한다.
• 메모리 오버헤드: 연결 리스트는 배열에 비해 포인터 공간을 추가로 사용해야 한다. 따라서 배열에 비해 추가적인 메모리가 사용된다.
• 복잡성: 연결 리스트는 포인터를 사용하기 때문에 배열보다 복잡하고 오류 발생의 가능성도 높다.

 

연결 리스트의 시간복잡도

---

• 접근(access): O(n)
• 탐색(find): O(n)
• 삽입(insertion): O(1)
• 삭제(deletion): O(1)

 

연결 리스트의 종류

---

• 단일 연결 리스트 (Singly Linked List): 각 노드는 다음 노드를 가리키는 하나의 포인터를 가지며 마지막 노드의 포인터는 null이다.
• 이중 연결 리스트 (Doubly Linked List): 각 노드는 다음 노드와 이전 노드를 가리키는 두 개의 포인터를 가지며 양방향으로 순회가 가능해 단일 연결 리스트에 비해 더 유연하다.
• 원형 연결 리스트 (Circular Linked List): 마지막 노드가 다시 첫 번째 노드를 가리키도록 연결되어 원형 구조를 이룬다. 단일 또는 이중 연결 리스트 형태로 구현될 수 있다.

 

연결 리스트의 구현

---

연결 리스트는 노드와 insert, delete 등의 메소드로 구성된다. 연결 리스트의 종류가 3가지이므로 글이 길어지는 관계로 구현은 다음 포스팅에 올리도록 하겠다.

 

궁금한 것이나 잘못된 것이 있다면 댓글에 남겨주세요!