연결 리스트(Linked List), 리스트(List)

Goal

• 연결 리스트의 특징을 이해하고 장단점을 말할 수 있다
• 연결 리스트를 구현할 수 있다
• 배열과 연결 리스트의 차이점을 알고 적절히 사용할 수 있다

---

연결 리스트(Linked List)

개념 : 각 노드를 간선으로 연결시켜 표현한 자료구조 또는 그러한 표현 기법

 

특징

일반적으로 배열과 반대되는 특징들을 가지고 있다

• 연속된 메모리 공간에 저장할 필요가 없다
• 임의 접근이 불가능하다
• 저장 공간의 활용이 자유롭다

 

장단점

연결 리스트는 포인터의 연결을 맺고 끊을 수 있기 때문에 다음과 같은 장단점이 있다

[장점]

• 삽입, 삭제가 용이하다
• 배열에 비해 저장 공간 활용이 자유롭다 => 필요할때 추가/삭제가 가능하기 때 낭비되는 메모리가 적고 크기 변환에 유연하다

[단점]

• 배열에 비해 탐색이 느리다 O(n) => 임의 접근(Random Access)가 불가능해서 순차 탐색을 해야 하기 때문
• 배열에 비해 캐시 적중률이 낮다 = > Cache Locality를 보장할 수 없기 때문
• 포인터를 위한 추가적인 메모리 공간이 필요 => 저장 공간의 overhead발생

종류

• 단일 연결 리스트(Singly Linked List)
• 이중 연결 리스트(Doubly Linked List)
• 원형 연결 리스트(Circular Linked List)

단일 연결 리스트(Singly Linked List)

단일 연결 리스트

노드간 연결이 한쪽 방향으로만 연결 되어 있는 연결 리스트 => 단방향 연결 리스트

 

이중 연결 리스트(Doubly Linked List)

이중 연결 리스트

노드간 연결이 양쪽 방향으로만 연결 되어 있는 연결 리스트 => 양방향 연결 리스트

 

원형 연결 리스트(Circular Linked List)

(단일) 원형 연결 리스트

시작 노드와 마지막 노드가 연결되어 있는 연결 리스트

 

배열 vs 연결 리스트

	배열	연결 리스트
원소 접근(탐색) 시간	O(1)	O(N)
임의 위치에 원소 삽입/삭제	O(N)	O(1)
메모리상 배치	연속	불연속
추가적으로 필요한 공간 (저장 공간상 Overhead가 발생하는지)	-	O(N)

참고) 연결 리스트는 삽입/삭제가 굉장히 빠르지만 탐색 후 삭제를 할 경우 탐색 시간에 영향을 많이 받는다

---

리스트(List)

임의 위치에서 원소의 삽입/삭제가 가능한 선형 자료구조

 

스택, 큐, 덱의 경우 특정 위치에서만 삽입 삭제가 가능(제한적 선형 자료구조)하지만 리스트의 경우 시작과 끝 뿐만 아니라 중간에 데이터를 삽입, 삭제하는 것이 가능한 자료구조이다.

 

'연결 리스트(Linked List)'와 '리스트(List)'란 용어가 다소 혼란스러울 수 있다. 리스트는 특정 자료구조를 의미하고, 연결 리스트는 어떤 자료구조를 구현하는 프로그래밍 기법이라고 생각하면 된다.

 

리스트의 추상 자료형(ADT)

객체 : 임의 접근 방법을 제공하는 같은 타입 요소들의 순서 있는 모임

연산

• insert(pos, x) : 리스트 pos위치에 x요소 삽입
• erase(pos) : pos 위치에 있는 요소 삭제
• isEmpty() : 리스트가 비어있는지 확인
• etc... : find(x), remove(x), push_front(), pop_front(), push_back(), pop_back(), size() 등 다양함 연산 정의 가능

리스트 구현 코드

- 단일 연결 리스트 - https://github.com/jihyuk124/DataStructure/tree/master/01.List/SinglyLinkedList

- 원형 이중 연결 리스트 -  https://github.com/jihyuk124/DataStructure/tree/master/01.List/DoublyLinkedList

 

References

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

https://blog.encrypted.gg/932?category=773649