💡 연결 리스트(Linked List) - 데이터 요소를 ‘노드(Node)’로 구성된 선형 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 링크(포인터)로 이루어져 있습니다.
- 연결 리스트는 동적 크기 조정이 용이하고, 삽입과 삭제가 빠르게 이루어질 수 있는 장점이 있습니다. - 하지만 특정 위치에 접근하는 데에는 선형적인 탐색이 필요하기 때문에 접근 속도가 느릴 수 있습니다. - 주로 데이터의 삽입과 삭제가 빈번하게 일어나는 상황에서 주로 사용됩니다. 큐(Queue)나 스택(Stack)과 같은 자료구조를 구현할 때 많이 활용됩니다. 또한 데이터 크기가 동적으로 변환하는 상황에서 유용하게 사용됩니다.
- 연결 리스트에서 각 노드가 다음 노드를 가리키는 역할을 합니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있으며, 이를 통해 노드들이 서로 연결되어 선형 자료구조를 형성합니다. - 링크(포인터)를 통해 다음 노드를 가리키기 때문에, 연결 리스트는 동적 크기 조정이 용이하고 빠른 삽입과 삭제가 가능합니다. 하지만 특정 위치에 접근하는 데에는 선형적인 탐색이 필요하기 때문에 접근 속도가 느릴 수 있습니다.
💡 선형 탐색 시간이란?
- 입력 크기에 비례하여 실행 시간이 증가하는 것을 의미합니다. 즉, 연결 리스트에서 특정 위치에 있는 요소에 접근하는 작업은 요소의 개수에 따라 시간이 선형적으로 증가합니다. 따라서 요소의 개수가 많을수록 접근 시간도 늘어날 수 있습니다.
1. LinkedList 특징
💡 연결 리스트 특징 1. 데이터 요소들이 노드(Node)들로 구성됩니다.
- 각 노드는 데이터와 다음 노드를 가리키는 포인터(참조)로 이루어져 있습니다.
2. 연결 리스트는 동적으로 크기가 조정될 수 있습니다.
- 요소의 추가나 삭제에 따라 리스트의 크기가 증가하거나 감소할 수 있습니다.
3. 삽입과 삭제 연산이 상대적으로 효율적입니다.
- 일반적으로 연결 리스트의 시작 또는 끝에 요소를 추가하거나 삭제하는 작업은 상수 시간에 이루어집니다. 하지만 특정 위치에 있는 요소에 접근하려면 포인터를 따라가야 하므로 선형 시간이 걸립니다.
4. 조회 시간이 상대적으로 시간이 걸립니다.
- 하나는 특정 위치에 있는 요소에 접근하는 것이 선형 시간이 걸린다는 것입니다. 따라서 조회 작업은 효율적이지 않을 수 있습니다.
5. 연결 리스트는 메모리를 효율적으로 사용할 수 있습니다.
- 각 노드는 필요한 만큼의 메모리를 차지하고, 요소의 추가 또는 삭제에 따라 메모리를 동적으로 할당하거나 해제할 수 있습니다.
[더 알아보기] 💡 왜 LinkedList는 조회 속도가 느린걸까?
- 포인터를 따라가야 하기 때문에 느립니다. 각 노드는 다음 노드를 가리키는 포인터를 가지고 있으며, 특정 위치의 요소에 접근하려면 해당 위치까지 포인터를 따라가야 합니다. 이러한 과정은 연결 리스트의 길이에 비례하여 시간이 걸리기 때문에 접근 시간이 길어집니다.
2. LinkedList 활용 : List, LinkedList 인터페이스를 사용한 차이
💡 List, LinkedList 인터페이스를 사용한 차이 💡 List 인터페이스를 사용한 경우
- 컬렉션 프레임워크의 List 인터페이스를 구현하는 모든 클래스의 객체로 처리할 수 있습니다. List 인터페이스는 공통으로 구현된 메서드 집합을 제공합니다.
💡 LinkedList 인터페이스를 사용하는 경우
- 컬렉션 프레임워크의 LinkedList 인터페이스에서 제공하는 특정 메서드와 기능에 액세스 하고 사용할 수 있습니다.
// List 인터페이스를 이용한 LinkedList 구현체 구성
List<String> strList = new LinkedList<>();
// LinkedList 인터페이스를 이용한 LinkedList 구현체 구성
LinkedList<String> strLinkedList = new LinkedList<>();
3. 시간복잡도
💡 시간 복잡도(Time Complexity)
- 알고리즘이 실행될 때 필요한 ‘입력 값’과 ‘연산 수행 시간’에 따라 효율적인 알고리즘을 나타내는 척도를 의미합니다. - 즉, 입력 값이 커질수록 알고리즘의 수행 시간이 어떻게 증가하는지에 따른 지표입니다.
- O(1) : 상수 시간 → O(log n) : 로그 시간 → O(n) : 선형 시간 → O(n log n) : 선형 로그 시간 → O(n^2) : 이차 시간 → O(2^n) : 지수 시간 → O(n!) : 팩토리얼 시간 순입니다.
💡 단순 연결 리스트(Singly Linked List) - 데이터 요소인 노드들이 ‘링크’로 연결되어 있는 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 링크로 이루어져 있습니다.
- 단순 연결 리스트는 ‘데이터의 삽입과 삭제가 빠르며 메모리 공간을 효율적으로 사용’할 수 있습니다. 삽입 또는 삭제하는 경우에는 단순히 링크를 변경하면 되므로, 배열과 같은 다른 데이터 구조에서 발생하는 데이터 이동이 필요하지 않습니다. - 그러나 데이터의 검색에는 선형적인 탐색이 필요하므로 효율성이 떨어질 수 있습니다. 특정 위치의 요소에 접근하기 위해서는 ‘헤드부터 순차적으로 탐색’ 해야 한다는 단점이 있습니다. - 많은 알고리즘과 데이터 구조에서 사용되며, 데이터의 동적 할당과 해제에 유용합니다. 또한, 스택(Stack)이나 큐(Queue)와 같은 다른 추상 자료형을 구현하는 데에도 활용됩니다.
4) 연결 리스트 종류: 이중 연결 리스트(Doubly Linked List)
💡 이중 연결 리스트(Double Linked List)
- 각 노드가 이전 노드와 다음 노드를 모두 가리키는 링크로 이루어져 있는 자료구조입니다. 양방향으로 탐색이 가능하며, 어떤 위치의 노드에서도 앞과 뒤의 노드에 접근할 수 있습니다.
- 이중 연결 리스트는 단순 연결 리스트와 달리 양방향으로 순회할 수 있으며, 양쪽 방향에서의 삽입과 삭제가 가능합니다. 이는 데이터의 검색과 수정을 효율적으로 처리할 수 있는 장점을 제공합니다. - 그러나 각 노드가 이전 노드와 다음 노드를 가리키는 링크를 유지해야 하므로, 메모리 사용량이 증가하게 됩니다. - 이중 연결 리스트는 데이터의 삽입 및 삭제 작업이 빈번하게 발생하는 상황에서 유용하게 사용됩니다. 또한, 이중 연결 리스트를 기반으로 구현된 많은 알고리즘과 데이터 구조가 존재하며, 예를 들어 LRU Cache와 같은 자료구조에서 활용됩니다.
💡 순환 연결 리스트(Circular Linked List) - 마지막 노드가 첫 번째 노드를 가리키는 형태로 이루어져 있는 자료구조입니다. 즉 리스트가 끝에서 시작으로 연결되는 원형 구조를 가지고 있습니다. 이러한 특성으로 인해 마지막 노드의 다음 노드가 첫 번째 노드가 되며, 첫 번째 노드의 이전 노드가 마지막 노드가 됩니다.
- 순환 연결 리스트는 데이터의 삽입과 삭제를 빠르게 처리할 수 있는 장점이 있습니다. 또한, 리스트의 시작과 끝이 연결되어 있으므로 순환 구조를 이용한 다양한 알고리즘을 구현할 수 있습니다. - 그러나 순환 연결 리스트를 순회하는 경우 무한 루프에 빠질 수 있으므로 조심해야 합니다. - 순환 연결 리스트는 리스트의 순서를 계속해서 이동하면서 작업을 수행해야 하는 경우에 유용합니다. 예를 들어, 원형 큐(Circular Queue)나 원형 버퍼(Circular Buffer)와 같이 순환적인 동작이 필요한 자료 구조에서 사용됩니다. 또한, 순환 연결 리스트는 알고리즘에서 반복적인 동작을 처리하는 데에도 활용될 수 있습니다.
