[DS] Linked Lists

Linked Lists란?

: 순차적인 노드들의 리스트로 각 노드는 데이터와 다음 노드에 대한 정보를 가지고 있다. 그렇기에 Array가 연속적인 메모리 블록이라고 했을때, Linked List는 비연속적으로 메모리 블록들이 연결되어 있다고 볼 수 있다. 구성 요소들은 다음과 같다.

Node: 데이터와 포인터의 집합

Pointer: 다음 노드로의 참조값

Head: Linked List의 첫번째 노드

Tail: Linked List의 마지막 노드

Singly Linked Lists

: 순방향으로만 연결된 Linked List

장점: 더 적은 메모리 사용 및 쉬운 구현

단점: 지나간 노드로 다시 갈 수 없음 (헤드노드에서 다음 노드로는 갈 수 있지만 다시 헤드노드로는 돌아갈 수 없음)

Doubly Linked Lists

:양방향으로 연결된 Linked List

장점: 지나간 노드로 돌아갈 수 있음

단점: 더 많은 메모리 사용.

Circular Linked Lists

: 테일이나 헤드가 NULL이 아닌 각각 첫번째 노드와 마지막 노드를 가르키는 경우.

---

Linked List 같은 경우 연속된 메모리를 할당받는 것이 아니기에 Index를 통한 원소에 대한 접근은 불가능하다. 그렇기에 각 원소에 접근하려면 Iterator라는 것이 필요한데, 이는 사실상 원소를 가르키는 임시 포인터이다. Linked List에 대해 모든 연산은 이 Iterator를 통해 한다.

Insert

4라는 값을 갖는 노드를 3번째 자리에 삽입한다고 하자.

Singly Linked Lists

1. Iterator를 2번째 노드로 이동시킨다.

2. 4라는 값을 가진 노드를 생성한 후 Iterator가 가르키는 노드의 포인터를 포인터로 지정한다.

3. Iterator가 가르키는 노드의 포인터를 새로운 노드로 바꾼다.

Doubly Linked Lists

1. 2번째 노드로 Iterator 이동

2. 4라는 값을 갖는 새로운 노드 생성 후 Iterator가 가르키는 노드와 그 다음 노드를 포인터로 지정한다.

3. 기존 3번째 노드의 이전노드 포인터를 새로운 노드로 바꾸고 2번째 노드의 다음노드 포인터도 새로운 노드로 바꾼다.

Delete 

3번째 노드를 삭제한다고 하자.

Singly Linked Lists

1. Iterator 2개를 각각 2번째와 3번째 노드로 이동

2. 3번째 노드에 새로운 포인터 Temp 생성 후 4번째 노드로 이동

3. 첫번째 Iterator 노드가 다른 Iterator 노드를 가르키게 설정

4. Temp가 가르키는 값 삭제. 

Doubly Linked Lists

1. Iterator를 세번째 노드로 이동

2. 세번째 노드의 다음노드의 이전노드 포인터를 세번째 노드 이전노드 포인터로 변경

3. 세번째 노드의 이전노드의 다음노드 포인터를 세번째 노드의 다음노드 포인터로 변경

4. 세번째 노드 삭제.

시간 복잡도

	Singly Linked List	Doubly Linked List
탐색(Search)	O(n)	O(n)
헤드에 삽입	O(1)	O(1)
테일에 삽입	O(1)	O(1)
헤드 삭제	O(1)	O(1)
테일 삭제	O(n)	O(1)
임의값 삭제	O(n)	O(n)

*Singly Linked Lists에서는 테일에 대한 참조값이 있어도 새로운 테일값에 접근할 수 없기 때문에 O(n)이 걸린다.