연결 리스트에 대해서 설명해주세요.
연결 리스트(Linked List) 는 리스트 내의 요소(노드)들을 포인터로 연결하여 관리하는 선형 자료구조입니다. 각 노드는 데이터와 다음 요소에 대한 포인터를 가지고 있는데요. 이때, 첫 번째 노드를 HEAD, 마지막 노드를 TAIL 이라고 합니다. 연결 리스트는 메모리가 허용하는 한 요소를 계속 삽입할 수 있으며, 시각 복잡도는 탐색에는 O(n), 노드 삽입과 삭제는 O(1)라는 특징을 가지고 있습니다. 해당 아이디어로 파생된 자료구조는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List, Circular Linked List)가 존재합니다.
배열은 순차적인 데이터가 들어가기 때문에 메모리 영역을 연속적으로 사용합니다. 반면, 연결 리스트는 메모리 공간에 흩어져서 존재한다는 점에서 배열과 차이가 있습니다.
단일 연결 리스트의 탐색, 추가, 삭제에 대해서 더욱 자세히 설명해 주세요. 🤔
class SinglyLinkedList {
public Node head;
public Node tail;
public Node insert(int newValue) {
Node newNode = new Node(null, newValue);
if (head == null) {
head = newNode;
} else {
tail.next = newNode;
}
tail = newNode;
return newNode;
}
public Node find(int findValue) {
Node currentNode = head;
while (currentNode.value != findValue) {
currentNode = currentNode.next;
}
return currentNode;
}
public void appendNext(Node prevNode, int value) {
prevNode.next = new Node(prevNode.next, value);
}
public void deleteNext(Node prevNode) {
if (prevNode.next != null) {
prevNode.next = prevNode.next.next;
}
}
}
단일 연결 리스트에서 탐색은 최악의 경우, 시간 복잡도는 O(n)입니다. 왜냐하면, 노드를 탐색하기 위해서 HEAD의 포인터부터 데이터를 찾을 때까지 다음 요소를 반복적으로 탐색하기 때문입니다.
삽입의 경우, 삽입될 위치 이전에 존재하는 노드와 신규 노드의 포인터를 조작하면 됩니다. 가령, 3번 위치에 신규 노드를 삽입해야 한다면 2번 위치에 있는 노드의 포인터를 신규 노드를 가리키도록 하고, 신규 노드의 포인터는 기존 3번 노드의 위치를 가리키도록 하면 됩니다. 삭제는 삭제할 노드의 이전 노드가 삭제 대상 노드의 다음 노드를 가리키도록 수정하고, 삭제 대상 노드를 메모리에서 지우면 됩니다. 삽입과 삭제 연산 자체의 경우 시간 복잡도는 O(1)이지만, 탐색이 필요한 경우 선형 시간이 걸립니다.