데이터 구조의 단일 연결 목록
사라 첸
단일 연결 목록이란 무엇입니까?
단일 연결 리스트(Singly Linked List)는 데이터가 노드에 저장되고 각 노드가 링크를 통해 다음 노드에 연결되는 선형 단방향 데이터 구조입니다. 각 노드에는 데이터 필드와 다음 노드에 대한 링크가 포함되어 있습니다. 단일 연결 목록은 한 방향으로만 이동할 수 있지만 이중 연결 목록은 양방향으로 이동할 수 있습니다.
단일 연결 목록의 노드 구조는 다음과 같습니다.
배열 대신 연결리스트를 사용하는 이유는 무엇입니까?
Linked List를 사용하는 것보다 Linked List를 사용하는 것이 더 나은 경우가 몇 가지 있습니다. 배열. 다음은 몇 가지 시나리오입니다.
- 알 수 없는 요소 수: 프로그램 런타임 중에 얼마나 많은 요소를 저장해야 하는지 모르는 경우 연결 목록을 사용할 수 있습니다. 연결된 목록에 요소를 추가하면 메모리가 동적으로 할당됩니다.
- 무작위 액세스: 요소에서 임의 액세스를 사용할 필요가 없는 시나리오에서는 연결 목록을 사용할 수 있습니다.
- 중간에 삽입: 배열 중간에 삽입하는 것은 복잡한 작업입니다. 다른 요소를 오른쪽으로 밀어야 하기 때문입니다. 그러나 연결 리스트를 사용하면 원하는 위치에 요소를 추가할 수 있습니다.
Opera단일 연결 목록의 종류
단일 연결 리스트는 메모리를 동적으로 할당하는 데 좋습니다. 연결 리스트의 모든 기본 연산, 즉 삽입, 삭제, 검색, 업데이트, 두 연결 리스트 병합, 순회 등을 제공합니다.
여기서는 연결 리스트의 다음 연산에 대해 논의해 보겠습니다.
- 머리에 삽입
- 꼬리에 삽입
- 노드 뒤에 삽입
- 노드 앞에 삽입
- 헤드 노드 삭제
- 꼬리 노드 삭제
- 노드 검색 및 삭제
- 연결리스트 순회
다음은 XNUMX개의 노드가 있는 연결 목록의 예입니다.
단일 연결 목록의 선두에 삽입
간단한 작업입니다. 일반적으로 단일 연결 리스트를 푸싱하는 것으로 알려져 있습니다. 새 노드를 만들고 이를 연결 리스트의 머리에 두어야 합니다.
이 작업을 수행하려면 두 가지 중요한 조건을 따라야 합니다.
- 목록이 비어 있으면 새로 생성된 노드가 헤드 노드가 되고 헤드의 다음 노드는 "NULL"이 됩니다.
- 목록이 비어 있지 않으면 새 노드가 헤드 노드가 되고 다음 노드는 이전 헤드 노드를 가리킵니다.
연결된 목록의 선두에 노드를 삽입하는 의사 코드는 다음과 같습니다.
function insertAtHead( head, value ): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNode
단일 연결 목록 끝에 삽입
연결된 목록의 끝에 노드를 삽입하는 것은 헤드에 삽입하는 것과 몇 가지 유사합니다. 당신이 해야 할 일은 끝 노드나 꼬리 노드로 이동하는 것뿐입니다. 그런 다음 끝 노드의 "다음" 노드가 새로 생성된 노드를 가리킵니다. 헤드 노드가 null이면 새 노드가 헤드 노드가 됩니다.
단계는 다음과 같습니다.
단계 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: then head = head.next head.next = newNode newNode.next = NULL
단일 연결 목록의 노드 뒤에 삽입
노드 뒤에 삽입하는 작업은 두 부분으로 구성됩니다. 노드를 검색하고 검색된 노드 뒤에 연결합니다. 모든 노드를 순회해야 합니다. 각 노드에 대해 검색 요소와 일치해야 합니다. 일치하는 항목이 있으면 검색된 노드 뒤에 새 노드를 추가합니다.
단계는 다음과 같습니다.
단계 1) 현재 노드의 값이 검색 항목과 같아질 때까지 다음 노드를 순회합니다.
단계 2) 새 노드의 다음 포인터는 현재 노드의 다음 포인터가 됩니다.
단계 3) 현재 노드의 다음 노드가 새 노드가 됩니다.
다음은 노드 뒤에 노드를 삽입하는 의사 코드입니다.
function insertAfter( head, value, searchItem ): newNode = Node(value) while head.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
단일 연결 목록의 노드 앞에 삽입
이 기능은 노드 뒤에 삽입하는 것과 매우 유사합니다. 새로운 노드를 생성하고 현재 노드가 검색 노드와 일치할 때까지 연결 리스트를 순회해야 합니다. 그런 다음 새 노드를 현재 노드의 이전 노드로 추가합니다.
단계는 다음과 같습니다.
단계 1) 다음 노드의 값이 검색 항목과 같아질 때까지 순회합니다.
단계 2) 새 노드를 생성하고 현재 노드의 다음 노드 옆에 노드의 "다음"을 할당합니다.
단계 3) 새 노드를 현재 노드의 다음 노드로 할당합니다.
의사 코드는 다음과 같습니다.
function insertBefore( head, value, searchItem ): newNode = Node(value) while head.next.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
단일 연결 리스트의 헤드 삭제
연결 리스트의 모든 함수에서 헤드 포인터가 매개변수로 제공됩니다. 헤드 노드를 삭제하고 헤드 노드의 다음 노드를 연결 리스트의 새 헤드로 만들어야 합니다. 또한 삭제된 노드의 메모리를 해제해야 합니다. 그렇지 않으면 다른 프로그램이 메모리에 액세스하려고 할 때 메모리가 점유된 것으로 표시됩니다.
단일 연결 리스트의 헤드를 삭제하는 단계는 다음과 같습니다.
단계 1) 헤드 노드의 다음 노드를 새 헤드로 할당합니다.
단계 2) 이전 헤드 노드에서 할당된 메모리를 해제합니다.
단계 3) 새 헤드 노드를 반환합니다.
헤드 노드 삭제를 위한 의사 코드:
function deleteHead( head ): temp = head head = head.next free( temp ) return head
단일 연결 리스트의 꼬리 삭제
tail 노드를 삭제하는 것은 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) 이전 노드의 "다음"은 현재 노드의 다음 노드가 됩니다.
단계 4) 현재 노드의 메모리를 삭제하고 해제합니다.
단일 연결 리스트에서 노드를 검색하고 삭제하기 위한 의사 코드:
function searchAndDelete( head, searchItem ): while head.next.next is not NULL and head.next.value is not equals searchItem : head = head.next head.next = head.next.next delete(head.next)
단일 연결 리스트 순회
단일 연결 목록에는 머리에서 꼬리까지 순회하는 기능만 있습니다. 이전 노드에 대한 포인터 포인트가 없습니다. 이것이 바로 단일 연결 목록을 역순으로 탐색할 수 없는 이유입니다. 우리는 각 노드를 순회하고 null을 얻을 때까지 현재 노드의 값을 인쇄합니다.
단계는 다음과 같습니다.
단계 1) 다음 노드로 null이 나올 때까지 각 노드를 탐색합니다.
단계 2) 현재 노드의 값을 인쇄합니다.
단일 연결 리스트를 순회하는 의사 코드:
function traverse( head ): while head.next is not NULL: print the value of the head 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);
}
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 = new Node();
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);
}else{
currentNode = currentNode->next;
}
}
}
cout<<"Deleted Node\t"<<searchItem<<endl;
return;
}
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 = new 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.')
return
def insertAtEnd(self,value):
if self.head is None:
self.insertAtHead(value)
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):
temp = Node()
if self.head is searchItem:
temp = self.head
self.head = self.head.next
else:
currentNode = self.head
while currentNode.next is not None:
if currentNode.next.data is searchItem:
temp = currentNode.next
currentNode.next = currentNode.next.next
else:
currentNode = currentNode.next
print(f'Deleted node\t{searchItem}')
return
def insertAfter(self,searchItem,value):
newNode = Node(data=value)
temp = self.head
while temp.next is not None and temp.data is not searchItem:
temp = temp.next
newNode.next = temp.next
temp.next = newNode
print(f'Inserted {value} after node\t{searchItem}')
return
def insertbefore(self,searchItem,value):
newNode = Node(data=value)
temp = self.head
while temp.next is not None and temp.next.data is not searchItem:
temp = temp.next
newNode.next = temp.next
temp.next = newNode
print(f'Inserted {value} before node\t{searchItem}')
return
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)로 수행될 수 있습니다.
평균적인 경우의 시간 복잡도:
- 단일 연결 목록에 "n"개의 요소가 있는 경우 연결 목록 내부에 삽입하려면 O(n)이 필요합니다.
- 검색 요소가 꼬리 노드에 있을 수 있으므로 검색 및 삭제에도 O(n)이 걸릴 수 있습니다. 이 경우 전체 목록을 순회해야 합니다.
단일 연결 리스트의 공간 복잡도
단일 연결 리스트는 동적으로 메모리를 할당합니다. n개의 요소를 저장하려면 n개의 메모리 단위를 할당합니다. 따라서 공간 복잡도는 O(n)입니다.
