- 자료구조의 하나로, 각
노드를 연결한 것(연결된 것을리스트라고 한다) - 노드는 데이터와 다른 노드를 가리키는 포인터로 구성
- 삽입연산, 제거연산, 탐색연산
- 배열과는 완전히 다른 구조로, 다른 방식으로 연산을 한다
1.1. Singly Linked List
- 노드 : 데이터, 다음 노드를 가리키고 있는 포인터로 구성
- 장점 : 삽입 또는 제거시 앞뒤로 밀거나 당기는 연산이 없어서 시간손실이 배열보다 적다 head와 tail로 각각 맨앞의 요소 탐색, 맨뒤의 요소 탐색을 빠르게 할 수있다
- 단점 : head, tail 이 아닌 특정부분 탐색의 경우 해당지점까지 순차적으로 탐색해야 하므로 배열에 비해 탐색시간이 많이 걸린다
1.2. Doubly Linked List
- 노드 : 데이터, 다음 노드를 가리키고 있는 포인터, 이전 노드를 가리키고 있는 포인터로 구성
- 장점 : 단방향 탐색만 가능한 singly linked list와 달리 양방향 탐색이 가능하다. 즉 tail에서 더 가까운 경우 tail부터 탐색을 하게 되어 singly linked list보다는 탐색이 빠르다. 연산도 간단해진다
- 단점 : 역시 탐색속도가 배열보다는 느리다
1.3. Circular Lniked List
- 노드 : 데이터, 다음 노드를 가리키고 있는 포인터로 구성. 단, tail은 head를 가리킨다
- 장점 : 순환형 자료구조에 적합하다
- 유의사항 : 인덱스의 값에 따라 연산 시 어느 노드를 가리키는 것인지 헷갈릴 수 있어 이 부분을 명확하게 하는 것이 중요하다. 노드추가 연산을 예로 들면, 인덱스가 0인 곳에 새로운 노드를 추가할 경우 head를 옮길 것인지 아니면 head를 그대로 둘 것인지 명확히 해야한다. 또 인덱스가 -1인 경우에 head 직전에 추가할 것인지 tail 직전에 추가할 것인지 명확히 할 필요가 있다.
💬 linked list와 array의 차이점
- 삽입연산이나 제거연산에서는 linked list가 유리하다
- 탐색에서는 array가 유리하다
- 메모리를 연속적으로 할당하는 array와 달리, linked list는 각 노드가 다음 노드의 주소(doubly면 이전까지)도 갖고있어야 하므로 메모리가 더 많이 소요된다
- 하지만 배열에서는 초기에 미리 그 크기를 크게 정해놓고 사용하는 것에 비해 연결리스트의 경우 자료가 입력될 때마다 동적할당으로 새로운 메모리 주소에 값을 할당하고 이전 자료와 연결해주기 때문에 이 점에서는 메모리 관리가 용이하다고 할 수 있다