LinkedList
LinkedList 는 메모리 상에서는 데이터가 불연속적으로 저장되어 있으나, 논리적으로 연속성을 구현한 선형 자료구조입니다.
- 값(Value)와 다음 값의 위치를(메모리 주소)를
노드(Node)라는 이름의 쌍으로 저장합니다. - i 번째 데이터에 접근(Access) & 변경(Modify)에
O(N)이 소요됩니다. - X 라는 데이터가 있는지 탐색하는데에는
O(N)이 소요됩니다. - 데이터의 삽입 & 삭제는 해당 노드에 접근하는 시간 & 이전 노드를 찾는 시간
O(N)을 제외하고, 어느 위치에서든O(1)이 소요됩니다.
LinkedList는 메모리상에 데이터가 불연속적으로 저장되기 때문에, 배열처럼 인덱스를 통한 랜덤 액세스가 불가능합니다. 따라서 특정 위치에 삽입 또는 삭제를 하기 위해서는 순차 탐색을 통해 이전 노드를 먼저 찾아야 합니다.
Access & Modify
링크드 리스트에서 i 번째 데이터에 접근(Access) & 변경(Modify)은 O(N)이 소요됩니다. 링크드 리스트의 데이터는 메모리상에 불연속적으로 저장되기 때문에, 배열처럼 인덱스를 통한 랜덤 액세스가 불가능하기 때문입니다. 따라서 Head 부터 i 번째 노드까지 순차탐색을 진행합니다.
프로그래밍 언어마다 링크드 리스트의 특정 Index 에 접근할 수 있는 메서드를 제공하지만, 이는 내부적으로 링크드 리스트의 Head부터 Index까지 순차탐색을 진행합니다.
데이터의 변경 또한 마찬가지입니다. 변경하고자 하는 노드를 탐색하는데 N이 소요되고, 값을 변경하는데 1이 소요되기 때문에 결국 O(N)의 시간복잡도를 가집니다.
Insertion
링크드 리스트에서 데이터를 삽입하는 데에는 삽입하려는 Index에 접근하는 시간 O(N)을 제외하면, 실제 삽입 연산은 어느 위치에서든 O(1) 만에 처리됩니다. 링크드 리스트의 특정 위치에 새로운 노드를 삽입하는 과정은 다음과 같습니다.
- 삽입하고자 하는 Index의 노드까지 순차적으로 탐색합니다.
- 새로운 노드를 생성합니다. 이때 노드의
value는 원하는 값으로 설정하고,다음 노드를 가리키는 포인터(next)는 일단null로 초기화합니다. 삽입 위치의 이전 노드의 next 포인터를 새로 생성한 노드를 가리키도록 수정합니다. 이어서새 노드의 next 포인터는 원래 삽입 위치에 있던 노드(즉, 이전 노드가 가리키고 있던 노드)를 가리키도록 설정합니다.
삽입하려는 Index에 접근해야 하는 이유는, 새 노드를 기존 노드들 사이에 정확히 끼워 넣기 위해 해당 위치의 이전 노드와 현재 노드의 포인터 정보를 알아야 하기 때문입니다.
이 과정을 이해하기 위해 그림을 통해 확인해 볼 수 있습니다. 현재 삽입하려는 노드의 인덱스는 3입니다. 삽입하고자 하는 Index의 노드까지 순차적으로 탐색합니다.
새로운 노드를 생성합니다. 이때, 노드의 value는 원하는 값으로, 다음 노드를 가리키는 포인터(next)는 일단 null로 초기화합니다.
삽입 위치의 이전 노드의 next 포인터를 새로 생성한 노드를 가리키도록 변경합니다. 이어서 새로 생성한 노드의 next 포인터를 원래 삽입 위치에 있던 노드(즉, 이전 노드가 가리키고 있던 노드)로 지정합니다.
Removal
링크드 리스트에서 데이터를 삭제하는 데에는 삭제하려는 Index에 접근하는 시간 O(N)을 제외하면, 실제 삭제 연산은 어느 위치에서든 O(1) 만에 처리됩니다. 이는 링크드 리스트에서 데이터를 삽입하는 시간복잡도와 동일합니다. 링크드 리스트의 특정 위치에 있는 노드를 삭제하는 과정은 다음과 같습니다.
- 삭제하고자 하는 Index의 노드까지 순차적으로 탐색합니다.
삭제 대상 노드의 이전 노드의 next 포인터를, 삭제 대상 노드가 가리키고 있던 다음 노드를 가리키도록 수정합니다.- 삭제 대상 노드 메모리를 해제합니다.
Java 를 기준으로 삭제 대상 노드는 더 이상 어떤 노드와도 연결되어 있지 않으므로, GC의 대상이 됩니다.
이 과정을 이해하기 위해 그림을 통해 확인해 볼 수 있습니다. 현재 삭제하려는 노드의 인덱스는 3입니다. 삭제하고자 하는 Index의 노드까지 순차적으로 탐색합니다.
삭제 대상 노드의 이전 노드의 next 포인터를, 삭제 대상 노드가 가리키고 있던 다음 노드를 가리키도록 수정합니다.
