[자료구조] 연결 리스트 Linked List

연결리스트(Linked List)란?

• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
• 각 노드는 다음 노드를 가리키는 포인터를 포함하고 있음
• 다음 노드를 가리키는 포인터는 다음 노드의 주소를 값으로 가짐
• 각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값으로 가짐
• 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조

연결리스트(Linked List)의 장점

1. 데이터 공간을 미리 할당하지 않아도 됨 (동적 크기)
2. 삭제나 추가가 O(1) 시간에 가능

연결리스트(Linked List)의 단점

1. 임의로 액세스를 허용할 수 없음 (첫 번째 노드부터 순차적으로 요소에 액세스 해야함)
2. 포인터의 여분의 메모리 공간이 목록의 각 요소에 필요
3. 특정 데이터를 검색하는데 무조건 O(n)의 시간이 걸림

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

1. 단일 연결리스트

• 가장 단순한 형태의 연결 리스트
• 각 노드 당 한 개의 포인터가 있고 포인터는 다음 노드의 위치를 가리킴
• 테일은 가장 마지막이므로 다음을 가리키는 포인터를 갖지 않음

2. 이중 연결리스트

• 순차적으로 자신이 원하는 데이터까지 하나하나 다 훑고 가야 하는 단방향 연결 리스트의 단점을 보완한 연결 리스트
• '다음 데이터의 주소 값' 그리고 '이전 데이터의 주소 값'을 가지고 있는 연결 리스트
• 뒤로 탐색하는 속도가 빠름
• 중간에 노드를 삭제하고 남아있는 노드끼리 연결하거나, 요소를 중간에 추가하기가 쉬움
• 참조가 2개나 있기 때문에 삽입이나 정렬할 경우 해야 할 작업이 더 많으며 자료구조의 크기가 단방향보다 조금 더 커짐

3. 원형 연결리스트

• 마지막 tail의 원소가 nil대신, head의 처음 원소를 가리키는 연결 리스트
• 단일 연결 리스트의 테일에 포인터가 추가된 형태
• 마지막 노드와 첫 번째 노드가 연결되어 있기 때문에 링크를 따라 순회하면 이전 노드에 접근할 수 있음

 

참고자료

- [자료구조] 연결리스트(Linked List)의 개념, 이해 | 단순연결리스트(Singly linked list) C언어 구현, 소스코드

- [Data Structure] 연결리스트에 대해 알아보자(Linked List)

- [자료구조] 연결 리스트(Linked List) 개념과 구현

- [자료구조] 연결 리스트(Linked List)는 무엇일까?