LinkedList란?
LinkedList는 데이터를 일렬로 연결하여 저장하는 자료 구조입니다.
LinkedList는 각각의 데이터를 노드(node)라고 부르는 객체로 표현합니다. 각각의 노드는 데이터를 저장하는 필드와 다음 노드를 가리키는 포인터(Pointer) 필드로 구성되어 있습니다. 이러한 구조는 데이터를 순차적으로 탐색하면서 필요한 데이터에 빠르게 접근할 수 있도록 합니다.
LinkedList 특징
- 동적 크기: LinkedList는 미리 고정된 크기가 없기 때문에 데이터를 동적으로 추가하거나 삭제할 수 있습니다. 이는 배열과 달리 크기가 동적으로 조정될 수 있다는 장점을 가지고 있습니다.
- 메모리 절약: LinkedList는 데이터를 연속된 메모리 공간에 저장하지 않으므로 배열에 비해 메모리를 효율적으로 사용할 수 있습니다. 또한, LinkedList는 동적으로 크기가 조정될 수 있기 때문에 메모리를 미리 할당하지 않아도 되는 장점이 있습니다.
- 순차적인 데이터 접근: LinkedList는 데이터가 연결되어 있기 때문에, 데이터에 접근할 때 순차적으로 접근해야 합니다. 이는 배열과 달리 임의의 인덱스로 데이터에 접근하는 것이 불가능하다는 단점을 가지고 있습니다.
- 포인터: LinkedList는 각각의 노드가 데이터와 포인터로 구성되어 있습니다. 포인터는 다음 노드를 가리키는데, 이는 연결리스트라는 이름의 유래가 되었습니다. 이러한 포인터는 데이터에 접근할 때 추가적인 작업이 필요하기 때문에 일반적으로 배열보다는 느립니다.
LinkedList 주요 메서드
- add(element): 맨 끝에 새로운 요소를 추가
- add(index, element): 특정 위치에 새로운 요소를 추가
- remove(): 맨 끝 요소를 제거하고 반환
- remove(index): 특정 위치에 있는 요소를 제거
- get(index): 특정 위치에 있는 요소를 반환
- set(index, element): 특정 위치에 있는 요소를 변경
- size(): 크기를 반환
- clear(): 모든 요소를 제거
- isEmpty(): 비어 있는지 여부를 반환
- contains(element): 특정 요소가 포함되어 있는지 여부를 반환
LinkedList 장단점
장점
- 동적 크기: 동적으로 크기가 조정될 수 있어서 데이터를 동적으로 추가하거나 삭제할 수 있습니다.
- 메모리 절약: 데이터를 연속된 메모리 공간에 저장하지 않으므로 배열에 비해 메모리를 효율적으로 사용할 수 있습니다.
- 데이터 추가/삭제: 데이터를 추가하거나 삭제할 때, 해당 노드를 찾는 것만으로도 시간 복잡도가 O(n)으로 매우 빠르게 처리됩니다. 이는 배열과 달리 데이터를 이동시키지 않아도 되므로 추가/삭제 작업이 매우 효율적으로 처리됩니다.
단점
- 순차적인 데이터 접근: 데이터가 연결되어 있기 때문에 데이터에 접근할 때 순차적으로 접근해야 합니다. 이는 배열과 달리 임의의 인덱스로 데이터에 접근하는 것이 불가능합니다. => 검색에 비효율적
- 포인터 오버헤드: 데이터에 접근할 때 추가적인 작업이 필요하기 때문에 배열보다는 일반적으로 느립니다.
- 불연속적인 메모리 접근: 데이터가 불연속적인 메모리에 저장되므로, CPU 캐시 성능을 낮출 수 있습니다. 이는 배열에 비해 처리 속도가 느릴 수 있다는 단점을 가지고 있습니다.
LinkedList 시간복잡도
- 삽입(add) : O(1)
- 삭제(remove) : O(1)
LinkedList는 중간에 노드를 삽입/삭제하는 경우 배열과 달리 데이터를 이동시키지 않아도 되므로 삽입/삭제 작업의 시간 복잡도는 O(1)입니다. 그러나 해당 노드를 찾는 과정에서 최악의 경우 O(n)의 시간 복잡도가 발생할 수 있습니다.
- 검색(search) : O(n)
- 특정 노드를 찾는 작업의 시간 복잡도는 최악의 경우 O(n)입니다. 이는 노드를 순차적으로 탐색해야 하기 때문입니다. 만약 검색 작업이 빈번하게 수행되는 경우, 검색 성능이 떨어지는 단점이 있습니다.
- 접근 : O(n)
- 각 노드에 직접적으로 접근할 수 없으므로 특정 노드에 접근하기 위해서는 처음부터 해당 노드까지 순차적으로 탐색해야 합니다. 따라서 LinkedList에서 특정 노드에 접근하는 작업의 시간 복잡도는 O(n)입니다.
- 순회: O(n)
- 전체 노드를 순회하는 작업의 시간 복잡도는 O(n)입니다. 이는 LinkedList의 모든 노드를 순차적으로 접근해야 하기 때문입니다.
복습해보기
