[자료구조 · 알고리즘] 연결 리스트 (Linked Lists)

어서와! 자료구조와 알고리즘은 처음이지? 강의 수강 후 내용을 정리한 글입니다.

 

자료 구조 정의

 

Node

- Data

- Link (next)

Head : 리스트의 맨 앞 요소

Tail : 리스트의 맨 끝 요소

of nodes : 연결리스트의 노드 갯수

 

 

연결 리스트의 각 원소들이 링크로 연결되어 있다.

 

배열은 인덱스로 지정되어 있지만 연결 리스트는 임의의 위치에서 연결할 수 있다. 물론 앞에서부터 하나하나 따라가다 보니 선형 탐색과 유사한 점이 있다.

하지만 선형 배열과 비교했을 때, 연결 리스트는 원소 가운데를 끊어 처리할 수 있기 때문에 원소 삽입 또는 삭제가 더 간단하다. 다만 저장 공간(메모리)의 소요가 더 크기 때문에 단점도 존재한다.

 

 

연산 정의

 

특정 원소 참조 (k번째) / 리스트 순회 / 길이 얻어내기 / 원소 삽입 / 원소 삭제 / 두 리스트 합치기

 

• k번째 원소 찾기

연결 리스트는 k번째의 원소를 찾기 위해서 앞에서부터 하나씩 링크를 따라가며 찾아간다.

이는 선형 배열에 비해 시간이 오래 걸린다. 선형 배열은 원소 번호에 따라 따라가면 되지만 연결 리스트는 링크를 거쳐가기 때문이다.

 

• 리스트 순회
• 길이 얻어내기

 

• 원소 삽입

3번째에 새로운 노드 삽입을 하기 위해서는, 2번째까지의 노드들은 그대로 유지하되, 3번째 이후의 노드들을 뒤로 하나씩 미룬다.

[pos-1 -> new node -> pos]

pos-1을 prev라고 했을 때

1) new node의 nex를 prev.next와 같은 pos로 가리킴

2) pos-1인 prev.next를 new node에 가리킴

3) nodeCount += 1

 

- 복잡도

맨 앞에 삽입하는 경우 : O(1)

중간에 삽입하는 경우 : O(n)

맨 뒤에 삽입하는 경우 : O(1)

(맨 앞, 맨 뒤는 바로 가능하니)

 

• 원소 삭제

pos가 가리키는 위치의 node 삭제 후, 그 node의 데이터 리턴

[ pos-1 -> pos -> pos+1 ]

1) prev, curr 노드 선언

2) prev.next -> curr.next

3) nodeCount -= 1

 

- 복잡도

맨 앞에 삭제하는 경우 : O(1)

중간에 삭제하는 경우 : O(n)

맨 뒤에 삭제하는 경우 : O(n)

(맨 뒤에서 삭제할 때 prev를 모르니 찾아야 함 = 삽입과의 차이점)

 

• 두 리스트의 연결

[리스트 L1, L2]

self.tail.newxt = L2.head (L1의 tail을 L2의 head로 연결)

self.tail = L2.taill