데이터 구조의 단일 연결 목록
사라 첸
⚡ 스마트 요약
단일 연결 리스트는 각 노드에 데이터와 다음 노드를 가리키는 포인터가 저장되는 선형의 단방향 데이터 구조입니다. 따라서 순회는 헤드에서 테일 방향으로만 이루어지며, 새 노드가 추가될 때마다 메모리가 동적으로 할당됩니다.
단일 연결 목록이란 무엇입니까?
단일 연결 리스트는 노드에 데이터가 저장되고 각 노드가 링크를 통해 다음 노드에 연결되는 선형적이고 단방향적인 데이터 구조입니다. 각 노드는 데이터 필드와 다음 노드로 연결되는 링크를 포함합니다. 단일 연결 리스트는 한 방향으로만 탐색할 수 있는 반면, 다중 연결 리스트는 양방향으로 탐색할 수 있습니다. 이중 연결 목록 양방향으로 통행할 수 있습니다.
다음은 단일 연결 리스트의 노드 구조입니다.
연결리스트의 노드 구조
배열 대신 연결 리스트를 사용하는 이유는 무엇일까요?
여러 시나리오에서 리스트가 리스트보다 유리한 경우가 있습니다. 배열:
- 알 수 없는 요소 수: 컴파일 시점에 필요한 요소 개수를 알 수 없는 경우, 연결 리스트는 요소가 추가될 때마다 메모리를 동적으로 할당합니다.
- 무작위 액세스: 임의 인덱스 접근이 필요하지 않은 경우 연결 리스트가 적합한 선택입니다.
- 중간에 삽입: 배열 중간에 요소를 삽입하려면 요소들을 이동시켜야 합니다. 하지만 연결 리스트는 몇 개의 포인터만 수정하면 어떤 위치에도 요소를 삽입할 수 있습니다.
Opera단일 연결 목록의 종류
단일 연결 리스트는 동적 메모리 할당에 적합합니다. 삽입, 삭제, 검색, 업데이트, 두 리스트 병합 및 순회와 같은 연결 리스트의 표준 연산을 지원합니다.
이 문서에서는 다음과 같은 작업에 대해 설명합니다.
- 머리에 삽입
- 꼬리에 삽입
- 노드 뒤에 삽입
- 노드 앞에 삽입
- 헤드 노드 삭제
- 꼬리 노드 삭제
- 노드 검색 및 삭제
- 연결리스트 순회
다음은 노드가 네 개인 연결 리스트의 예입니다.
단일 연결 목록의 예
단일 연결 리스트의 헤드에 삽입
이것은 간단한 연산입니다. 일반적으로 단일 연결 리스트에 노드를 추가하는 작업으로 알려져 있습니다. 새로운 노드가 생성되어 리스트의 맨 앞에 배치됩니다.
이 작업을 수행하려면 다음 두 가지 중요한 조건을 따라야 합니다.
- 리스트가 비어 있으면 새로 생성된 노드가 헤드 노드가 되고, 그 노드는... 다음 것 포인터가 NULL입니다.
- 리스트가 비어 있지 않으면 새 노드가 헤드 노드가 되고, 다음 것 포인터가 이전 헤드 노드를 가리킵니다.
다음은 연결 리스트의 헤드에 노드를 삽입하는 의사 코드입니다.
function insertAtHead(head, value): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNode
머리 부분에 삽입
단일 연결 리스트의 끝에 요소 삽입
연결 리스트의 끝에 노드를 삽입하는 것은 시작 부분에 삽입하는 것과 유사합니다. 끝 노드까지 이동한 다음, 해당 노드를 가리키도록 하면 됩니다. 다음 것 새 노드를 가리키는 포인터입니다. head가 NULL이면 새 노드가 head가 됩니다.
단계 1) 횡단하다 다음 것 현재 노드의 포인터가 NULL이 됩니다.
단계 2) 지정된 값으로 새 노드를 만듭니다.
단계 3) 새 노드를 꼬리 노드의 다음 노드로 할당합니다.
단일 리스트의 끝에 요소를 삽입하는 의사 코드는 다음과 같습니다.
function insertAtEnd(head, value): newNode = Node(value) if head is NULL: head = newNode return head while head.next is not NULL: head = head.next head.next = newNode newNode.next = NULL
꼬리 부분에 삽입
단일 연결 리스트에서 노드 뒤에 삽입
노드 뒤에 노드를 삽입하는 작업은 두 단계로 이루어집니다. 먼저 대상 노드를 찾고, 그 뒤에 새 노드를 연결합니다. 일치하는 노드를 찾을 때까지 리스트를 순회한 다음, 새 노드를 삽입합니다.
단계 1) 현재 노드의 값이 검색 항목과 같아질 때까지 순회합니다.
단계 2) 새 노드를 설정합니다. 다음 것 현재 노드를 가리키는 포인터 다음 것 바늘.
단계 3) 현재 노드를 가리킵니다. 다음 것 새 노드를 가리키는 포인터입니다.
의사 코드:
function insertAfter(head, value, searchItem): newNode = Node(value) while head.value != searchItem: head = head.next newNode.next = head.next head.next = newNode
단일 연결 목록의 노드 뒤에 노드 삽입
단일 연결 리스트에서 노드 앞에 삽입
이는 노드 뒤에 삽입하는 것과 유사합니다. 다음 노드가 검색 값과 일치할 때까지 순회한 다음, 새 노드를 그 앞에 삽입합니다.
단계 1) 다음 노드의 값이 검색 항목과 같아질 때까지 순회합니다.
단계 2) 새 노드를 생성하고 해당 노드의 속성을 설정합니다. 다음 것 현재 노드를 가리키는 포인터 다음 것.
단계 3) 현재 노드를 가리킵니다. 다음 것 새 노드로 이동합니다.
function insertBefore(head, value, searchItem): newNode = Node(value) while head.next.value != searchItem: head = head.next newNode.next = head.next head.next = newNode
단일 연결 목록의 노드 앞에 노드 삽입
단일 연결 리스트의 헤드를 삭제합니다.
헤드 포인터가 매개변수로 제공됩니다. 헤드 노드가 제거되고 다음 노드가 새로운 헤드가 됩니다. 메모리 누수를 방지하기 위해 삭제된 노드의 메모리를 해제해야 합니다.
단계 1) 헤드의 다음 노드를 새로운 헤드로 지정합니다.
단계 2) 이전 헤드 노드에 할당된 메모리를 해제합니다.
단계 3) 새 헤드 노드를 반환합니다.
function deleteHead(head): temp = head head = head.next free(temp) return head
연결리스트의 헤드 삭제
단일 연결 리스트의 꼬리 부분을 삭제합니다.
꼬리 노드를 삭제하는 것은 머리 노드를 삭제하는 것과 유사합니다. 차이점은 리스트의 끝까지 순회해야 한다는 것입니다. 단일 연결 리스트에서 꼬리 노드는 가장 중요한 노드입니다. 다음 것 포인터가 NULL이면 꼬리 노드입니다.
단계 1) 꼬리 노드 바로 앞까지 이동합니다. 현재 노드를 저장합니다.
단계 2) 다음 노드(꼬리)의 메모리를 해제합니다.
단계 3) 현재 노드의 다음 노드를 NULL로 설정합니다.
function deleteTail(head): while head.next.next is not NULL: head = head.next free(head.next) head.next = NULL
단일 연결 목록의 꼬리 삭제
단일 연결 리스트에서 노드를 검색하고 삭제하는 방법
이 함수는 검색과 삭제, 두 가지 작업을 수행합니다. 리스트의 끝까지 순회합니다. 일치하는 노드를 찾으면 해당 노드를 제거하고 이전 노드와의 연결을 다시 설정합니다. 다음 것 바늘.
단계 1) 리스트의 끝까지 순회합니다. 현재 노드가 검색 노드와 같은지 확인합니다.
단계 2) 일치하는 항목이 발견되면 현재 노드에 대한 포인터를 저장합니다.
단계 3) The 다음 것 이전 노드의 노드가 현재 노드의 다음 노드가 됩니다.
단계 4) 현재 노드를 삭제하고 메모리를 해제합니다.
function searchAndDelete(head, searchItem): while head.next.next is not NULL and head.next.value != searchItem: head = head.next temp = head.next head.next = head.next.next free(temp)
단일 연결 목록에서 노드 검색 및 삭제
단일 연결 리스트를 순회합니다.
단일 연결 리스트는 헤드에서 테일로만 순회할 수 있습니다. 이전 노드를 가리키는 포인터가 없으므로 역순회는 불가능합니다. 각 노드는 순서대로 방문되며, NULL에 도달할 때까지 해당 노드의 값이 출력됩니다.
단계 1) NULL에 도달할 때까지 각 노드를 순회합니다.
단계 2) 현재 노드의 값을 인쇄합니다.
function traverse(head): while head is not NULL: print head.value head = head.next
단일 연결 목록의 예 C++
#include<iostream> using namespace std; struct Node{ int data; struct Node *next; }; void insertAtHead(Node* &head, int value){ Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; if(head != NULL){ newNode->next = head; } head = newNode; cout<<"Added "<<newNode->data<<" at the front"<<endl; } void insertEnd(Node* &head, int value){ if(head == NULL){ insertAtHead(head, value); return; } Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; Node *temp = head; while(temp->next != NULL){ temp = temp->next; } temp->next = newNode; cout<<"Added "<<newNode->data<<" at the end"<<endl; } void searchAndDelete(Node **headPtr, int searchItem){ Node *temp = NULL; if((*headPtr)->data == searchItem){ temp = *headPtr; *headPtr = (*headPtr)->next; free(temp); } else { Node *currentNode = *headPtr; while(currentNode->next != NULL){ if(currentNode->next->data == searchItem){ temp = currentNode->next; currentNode->next = currentNode->next->next; free(temp); break; } else { currentNode = currentNode->next; } } } cout<<"Deleted Node\t"<<searchItem<<endl; } void insertAfter(Node* &headPtr, int searchItem, int value){ Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; Node *head = headPtr; while(head->next != NULL && head->data != searchItem){ head = head->next; } newNode->next = head->next; head->next = newNode; cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl; } void insertBefore(Node* &headPtr, int searchItem, int value){ Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; Node *head = headPtr; while(head->next != NULL && head->next->data != searchItem){ head = head->next; } newNode->next = head->next; head->next = newNode; cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl; } void traverse(Node *headPointer){ Node* tempNode = headPointer; cout<<"Traversal from head:\t"; while(tempNode != NULL){ cout<<tempNode->data; if(tempNode->next) cout<<" --> "; tempNode = tempNode->next; } cout<<endl; } int main(){ Node *head = NULL; insertAtHead(head, 5); insertAtHead(head, 6); insertAtHead(head, 7); insertEnd(head, 9); traverse(head); searchAndDelete(&head, 6); traverse(head); insertAfter(head, 7, 10); insertBefore(head, 9, 11); traverse(head); }
산출
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Traversal from head: 7 --> 6 --> 5 --> 9 Deleted Node 6 Traversal from head: 7 --> 5 --> 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversal from head: 7 --> 10 --> 5 --> 11 --> 9
단일 연결 목록의 예 Python
class Node: def __init__(self, data=None, next=None): self.data = data self.next = next class SinglyLinkedList: def __init__(self): self.head = None def insertAtHead(self, value): newNode = Node(data=value) if self.head is not None: newNode.next = self.head self.head = newNode print(f'Added {newNode.data} at the front.') def insertAtEnd(self, value): if self.head is None: self.insertAtHead(value) return newNode = Node(value) temp = self.head while temp.next is not None: temp = temp.next temp.next = newNode print(f'Added {newNode.data} at the end.') def searchAndDelete(self, searchItem): if self.head is None: return if self.head.data == searchItem: self.head = self.head.next print(f'Deleted node\t{searchItem}') return currentNode = self.head while currentNode.next is not None: if currentNode.next.data == searchItem: currentNode.next = currentNode.next.next print(f'Deleted node\t{searchItem}') return currentNode = currentNode.next def insertAfter(self, searchItem, value): newNode = Node(data=value) temp = self.head while temp.next is not None and temp.data != searchItem: temp = temp.next newNode.next = temp.next temp.next = newNode print(f'Inserted {value} after node\t{searchItem}') def insertBefore(self, searchItem, value): newNode = Node(data=value) temp = self.head while temp.next is not None and temp.next.data != searchItem: temp = temp.next newNode.next = temp.next temp.next = newNode print(f'Inserted {value} before node\t{searchItem}') def traverse(self): temp = self.head print("Traversing from head:\t", end="") while temp: print("{}\t".format(temp.data), end="") temp = temp.next print() singlyLinkedList = SinglyLinkedList() singlyLinkedList.insertAtHead(5) singlyLinkedList.insertAtHead(6) singlyLinkedList.insertAtHead(7) singlyLinkedList.insertAtEnd(9) singlyLinkedList.traverse() singlyLinkedList.searchAndDelete(6) singlyLinkedList.traverse() singlyLinkedList.insertAfter(7, 10) singlyLinkedList.insertBefore(9, 11) singlyLinkedList.traverse()
산출
Added 5 at the front. Added 6 at the front. Added 7 at the front. Added 9 at the end. Traversing from head: 7 6 5 9 Deleted node 6 Traversing from head: 7 5 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversing from head: 7 10 5 11 9
단일 연결 리스트의 복잡성
복잡도에는 시간 복잡도와 공간 복잡도 두 가지 종류가 있습니다. 단일 연결 리스트의 경우 최악의 경우와 평균적인 경우의 시간 복잡도는 동일합니다.
최고의 경우 시간 복잡도:
- 헤드에 삽입하는 것은 O(1)로 가능합니다. 리스트 내부를 순회할 필요가 없습니다.
- 대상 요소가 헤드 노드에 있는 경우 검색 및 삭제는 O(1)로 수행할 수 있습니다.
평균적인 경우의 시간 복잡도:
- 연결 리스트 내부 삽입은 O(n)의 시간이 걸립니다. n 요소의 총 개수입니다.
- 검색과 삭제도 O(n) 시간이 걸릴 수 있는데, 그 이유는 대상 요소가 테일 노드까지 어디에든 위치할 수 있기 때문입니다.
단일 연결 리스트의 공간 복잡도
단일 연결 리스트는 메모리를 동적으로 할당합니다. 저장하기 위해 n 요소를 할당합니다. n 메모리 단위입니다. 따라서 공간 복잡도는 O(n)입니다.
단일 연결 리스트의 응용
단일 연결 리스트는 순방향 탐색과 동적 메모리가 유용한 여러 곳에서 나타납니다.
- 스택과 큐: 노드로 구성된 LIFO 스택 및 FIFO 큐의 기본 저장소입니다.
- 해시 테이블 체이닝: 충돌은 각 버킷별로 단일 연결 리스트에 항목을 연결하여 해결합니다.
- 인접 목록: 희소 그래프는 각 정점에 대해 이웃 정점들의 단일 연결 리스트를 사용합니다.
- 심볼 표: 컴파일러와 인터프리터는 스코프별로 식별자를 단일 연결 리스트로 연결합니다.
- 메모리 할당자: 자유 목록 할당자 track개의 자유 블록을 단일 연결 리스트로 표현합니다.
