[자료구조] 배열, 연결리스트

연결리스트

• 연결리스트(Linked List)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.
• 각 노드는 다음 노드를 가리키는 포인터를 포함한다.

 

연결리스트의 종류

단순(단방향) 연결리스트

단일 연결 리스트(Singly linked list)는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

 

이중(양방향) 연결리스트

단순 연결 리스트(Singly Linked List)는 next로 현재 노드에서 다음 노드로 갈 수 있지만 이전 노드로는 갈 수 없다. 이러한 단점을 해결하기 위해 노드에 앞 노드의 메모리 주소를 보관하는 포인터 prev를 만들어준 형태를 이중 연결 리스트(Doubly Linked List)라고 한다.

 

원형 연결리스트

원형 연결 리스트(Circle linked List)란 단순 연결 리스트(Singly Linked List)의 마지막 노드의 포인터가 NULL이 아닌 헤드를 가리키는 형태의 리스트다. 따라서 리스트의 끝이 존재하지 않는다.

 

배열 vs 연결리스트

접근 시간 복잡도

배열: O(1)

인덱스 n의 요소에 바로 접근할 수 있다.

 

연결리스트: O(n)

인덱스 n의 요소에 접근하려면 연결된 링크를 따라 n번 이동한다.

 

탐색 시간 복잡도

배열: O(n)

0번째 인덱스 요소부터 마지막 인덱스 요소까지 접근하면서 원하는 데이터를 찾는다.

 

연결리스트: O(n)

배열과 동일하게 0번째 인덱스 요소부터 마지막 인덱스 요소까지 접근하면서 원하는 데이터를 찾는다.

 

삽입/삭제 시간 복잡도

배열: O(n)

데이터를 삽입, 삭제하기 위해 기존의 데이터를 옮기는 작업이 필요하다. 예를 들어 0번째 인덱스에 데이터를 삽입하기 위해서는 현재 배열의 0번째 인덱스부터 마지막 인덱스까지의 데이터들을 모두 한 칸씩 뒤로 옮겨야 한다. 하지만 배열의 마지막에 데이터를 삽입하거나 삭제하는 경우에는 O(1)의 시간 복잡도를 가진다.

 

연결리스트: O(1)

삽입, 삭제할 노드의 주변 노드들의 Link만 수정하면 된다. 따라서 삽입, 삭제 연산 자체는 시간 복잡도가 O(1)이다. 그렇지만 삽입, 삭제할 노드를 탐색하는 과정이 필요하기 때문에 최악의 경우 O(n)의 시간 복잡도가 필요하다. 만약 가장 앞이나 뒤에 삽입한다면 O(1)의 시간 복잡도를 가진다.

 

배열 or 연결리스트

• 데이터의 양이 많고 삽입/삭제가 없음. 데이터 검색을 많이 해야할 때 → 배열 사용
• 데이터의 양이 적고 삽입/삭제 빈번함 → 연결리스트 사용

 

---

참고 자료

https://hyeinisfree.tistory.com/64#recentComments

https://github.com/gyoogle/tech-interview-for-developer/blob/ed8c9810be6eb6404c13d9a03661809e6d27e8a0/Interview/Interview%20List.md?plain=1#L53