연결 리스트(Linked List)

연결 리스트(Linked List)란?

연결리스트는 각 노드가 데이터와 포인터를 가지고 있으며 소세지처럼 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 노드의 포인터가 다음이나 이전의 노드와 연결을 할 수 도 있다.

 

연결 리스트(Linked List)의 종류

단순 연결 리스트(Singly linked list)

단일 연결 리스트는 각 노드에 자료 저장공간과 포인터 공간(다른 노드를 연결 수 있는 공간)이 있고, 각 노드의 포인터는 다음 노드를 가르키게 된다.

단순 연결 리스트

이중 연결 리스트(Doubly linked list)

단순 연결 리스트는 현재 노드에서 다음 노드로 갈 수 있지만 이전 노드로 돌아 갈 수 없다.

이를 해결하기 위해 이전 노드를 가르키는 prev를 추가한 연결리스트 이다.

이중 연결 리스트

 

원형 연결 리스트(Circular linked list)

원형 연결 리스트는 단순 연결 리스트의 마지막 포인터가 null로 끝나는 것이 아닌 HEAD를 가리키는 연결 리스트를 말합니다.

원형 연결 리스트

 

연결 리스트(Linked List)의 시간 복잡도

접근 시간 복잡도: O(n)

• 인덱스 n에 있는 노드에 접근 시 HEAD에서 다음 노드로 n번 이동
• 최악의 경우 시간 복잡도 : O(n)

탐색 시간 복잡도: O(n)

• 배열 탐색 시와 동일
• 가장 앞의 노드부터 찾고자 하는 데이터가 나올 때 까지 탐색
• 최악의 경우 시간 복잡도 : O(n

삽입/삭제 시간 복잡도: O(1)

• 삽입 및 삭제할 노드의 주변 노드의 next 및 prev를 수정하면 된다.
• 시간 복잡도 : O(1)

배열(Array)의 시간 복잡도

접근 시간 복잡도: O(1)

• 인덱스 n에 바로 접근이 가능하다.

탐색 시간 복잡도: O(n)

• 0번째 인덱스부터 마지막 인덱스까지 원하는 데이터가 나올 때 까지 찾는다.
• 최악의 경우 시간 복잡도 : O(n)

삽입/삭제 시간 복잡도: O(n)

• 특정 인덱스에 데이터를 삽입 및 삭제시에는 기존의 데이터를 옮기는 작업이 필요로 한다.
• 배열 맨 앞에 데이터를 삽입 및 삭제하고자 할 때 기존의 데이터를 한 인덱스 씩 뒤로 및 앞으로 옮겨야 한다.

 

메모리 사용에 대한 관점

 

• 배열은 사용 전에 배열의 크기를 미리 선언해야 하기 때문에 메모리 사용에서 비효율적(정적 할당)
• 연결리스트는 필요할 때마다 노드를 생성하여 연결하기 때문에 메모리 사용에서 효율적(동적 할당)
• 배열은 메모리 공간의 연속적으로 저장되어있는 자료구조이기에 인덱스 접근이 용이하며 데이터외 노드 주소에대한 저장이 필요가 없다.
• 연결리스트는 데이터를 저장할 공간과 포인터 주소를 저장할 공간이 필요하다.

 

 

참고

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

https://hyeinisfree.tistory.com/64