linked list data structure c with illustration
C ++에서 연결된 목록에 대한 자세한 연구.
연결 목록은 데이터 항목을 저장하는 선형 동적 데이터 구조입니다. 기본 C ++에 대한 이전 주제에서 이미 배열을 보았습니다. 또한 배열은 연속 된 위치에 데이터 항목을 저장하는 선형 데이터 구조라는 것을 알고 있습니다.
배열과 달리 연결 목록은 인접한 메모리 위치에 데이터 항목을 저장하지 않습니다.
연결 목록은 두 부분을 포함하는 '노드'라는 항목으로 구성됩니다. 첫 번째 부분은 실제 데이터를 저장하고 두 번째 부분에는 다음 노드를 가리키는 포인터가 있습니다. 이 구조를 일반적으로 '단일 연결 목록'이라고합니다.
소프트웨어 테스트에서 테스트 데이터 생성
=> 여기에서 최고의 C ++ 교육 자습서를 확인하십시오.
학습 내용 :
C ++의 연결된 목록
이 자습서에서는 단일 연결 목록을 자세히 살펴 보겠습니다.
다음 다이어그램은 단일 연결 목록의 구조를 보여줍니다.
위와 같이 링크드리스트의 첫 번째 노드를“head”라고하고 마지막 노드를“Tail”이라고합니다. 보시다시피 연결된 목록의 마지막 노드는 가리키는 메모리 주소가 없기 때문에 다음 포인터를 null로 갖습니다.
각 노드에는 다음 노드에 대한 포인터가 있으므로 연결 목록의 데이터 항목은 연속 위치에 저장할 필요가 없습니다. 노드는 메모리에 흩어져있을 수 있습니다. 각 노드는 다음 노드의 주소를 가지므로 언제든지 노드에 액세스 할 수 있습니다.
연결 목록에 데이터 항목을 추가하고 목록에서 항목을 쉽게 삭제할 수 있습니다. 따라서 연결 목록을 동적으로 늘리거나 줄일 수 있습니다. 연결 목록에있을 수있는 데이터 항목 수에는 상한선이 없습니다. 메모리를 사용할 수있는 한 링크 된 목록에 추가 된 데이터 항목을 많이 가질 수 있습니다.
손쉬운 삽입 및 삭제 외에도 연결 목록은 연결 목록에 필요한 항목 수를 미리 지정할 필요가 없기 때문에 메모리 공간을 낭비하지 않습니다. 연결된 목록이 차지하는 유일한 공간은 약간의 오버 헤드를 추가하는 다음 노드에 대한 포인터를 저장하는 것입니다.
다음으로 연결 목록에서 수행 할 수있는 다양한 작업에 대해 설명합니다.
운영
다른 데이터 구조와 마찬가지로 연결된 목록에 대해서도 다양한 작업을 수행 할 수 있습니다. 그러나 배열과는 달리 첨자를 사용하여 요소가 중간에 있더라도 직접 액세스 할 수있는 배열과 달리 연결 목록으로 동일한 임의 액세스를 수행 할 수 없습니다.
모든 노드에 액세스하려면 처음부터 연결 목록을 탐색해야합니다. 그러면 원하는 노드에 액세스 할 수 있습니다. 따라서 연결된 목록에서 무작위로 데이터에 액세스하는 것은 비용이 많이 듭니다.
다음과 같이 연결된 목록에서 다양한 작업을 수행 할 수 있습니다.
# 1) 삽입
연결 목록 삽입 작업은 연결 목록에 항목을 추가합니다. 간단하게 들릴지 모르지만 연결된 목록의 구조를 고려할 때 데이터 항목이 연결 목록에 추가 될 때마다 삽입 한 새 항목의 이전 노드와 다음 노드의 다음 포인터를 변경해야한다는 것을 알고 있습니다.
두 번째로 고려해야 할 사항은 새 데이터 항목이 추가 될 위치입니다.
연결 목록에는 데이터 항목을 추가 할 수있는 세 위치가 있습니다.
# 1) 연결 목록의 시작 부분
연결된 목록은 2-> 4-> 6-> 8-> 10 아래에 표시됩니다. 새 노드 1을 목록의 첫 번째 노드로 추가하려면 노드 2를 가리키는 헤드가 이제 1을 가리키고 노드 1의 다음 포인터는 아래에 표시된 것처럼 노드 2의 메모리 주소를 갖게됩니다. 그림.
따라서 새로운 연결 목록은 1-> 2-> 4-> 6-> 8-> 10이됩니다.
# 2) 주어진 노드 이후
배열 자바를 복사하는 방법
여기에 노드가 주어지고 주어진 노드 뒤에 새 노드를 추가해야합니다. 아래 링크 된 목록 a-> b-> c-> d-> e에서 노드 c 다음에 노드 f를 추가하려면 링크 된 목록은 다음과 같습니다.
따라서 위의 다이어그램에서 주어진 노드가 있는지 확인합니다. 있는 경우 새 노드 f를 만듭니다. 그런 다음 노드 c의 다음 포인터를 새 노드 f를 가리 킵니다. 노드 f의 다음 포인터는 이제 노드 d를 가리 킵니다.
# 3) 연결 목록 끝
세 번째 경우에는 연결 목록 끝에 새 노드를 추가합니다. 동일한 연결 목록 a-> b-> c-> d-> e가 있고 목록 끝에 노드 f를 추가해야한다고 가정합니다. 노드를 추가하면 연결 목록이 아래와 같이 표시됩니다.
따라서 우리는 새로운 노드 f를 만듭니다. 그런 다음 널을 가리키는 꼬리 포인터는 f를 가리키고 노드 f의 다음 포인터는 널을 가리 킵니다. 아래의 C ++ 프로그램에서 세 가지 유형의 삽입 함수를 모두 구현했습니다.
C ++에서는 연결 목록을 구조 또는 클래스로 선언 할 수 있습니다. 연결 목록을 구조로 선언하는 것은 전통적인 C 스타일 선언입니다. 클래스로서의 연결 목록은 대부분 표준 템플릿 라이브러리를 사용하는 동안 최신 C ++에서 사용됩니다.
다음 프로그램에서는 구조를 사용하여 연결 목록을 선언하고 생성했습니다. 멤버로 다음 요소에 대한 데이터와 포인터가 있습니다.
#include using namespace std; // A linked list node struct Node { int data; struct Node *next; }; //insert a new node in front of the list void push(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; /* 2. assign data to node */ newNode->data = node_data; /* 3. set next of new node as head */ newNode->next = (*head); /* 4. move the head to point to the new node */ (*head) = newNode; } //insert new node after a given node void insertAfter(struct Node* prev_node, int node_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { coutnext = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = newNode; } /* insert new node at the end of the linked list */ void append(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; struct Node *last = *head; /* used in step 5*/ /* 2. assign data to the node */ newNode->data = node_data; /* 3. set next pointer of new node to null as its the last node*/ newNode->next = NULL; /* 4. if list is empty, new node becomes first node */ if (*head == NULL) { *head = newNode; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = newNode; return; } // display linked list contents void displayList(struct Node *node) { //traverse the list to display each node while (node != NULL) { coutnext; } if(node== NULL) cout 산출:
최종 연결 목록 :
30–> 20–> 50–> 10–> 40–> null
다음으로, 우리는 Java에서 연결 목록 삽입 작업을 구현합니다. Java 언어에서 연결 목록은 클래스로 구현됩니다. 아래 프로그램은 C ++ 프로그램과 논리가 비슷하지만 링크드리스트에 클래스를 사용한다는 점만 다릅니다.
class LinkedList { Node head; // head of list //linked list node declaration class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Insert a new node at the front of the list */ public void push(int new_data) { //allocate and assign data to the node Node newNode = new Node(new_data); //new node becomes head of linked list newNode.next = head; //head points to new node head = newNode; } // Given a node,prev_node insert node after prev_node public void insertAfter(Node prev_node, int new_data) { //check if prev_node is null. if (prev_node == null) { System.out.println('The given node is required and cannot be null'); return; } //allocate node and assign data to it Node newNode = new Node(new_data); //next of new Node is next of prev_node newNode.next = prev_node.next; //prev_node->next is the new node. prev_node.next = newNode; } //inserts a new node at the end of the list public void append(intnew_data) { //allocate the node and assign data Node newNode = new Node(new_data); //if linked list is empty, then new node will be the head if (head == null) { head = new Node(new_data); return; } //set next of new node to null as this is the last node newNode.next = null; // if not the head node traverse the list and add it to the last Node last = head; while (last.next != null) last = last.next; //next of last becomes new node last.next = newNode; return; } //display contents of linked list public void displayList() { Node pnode = head; while (pnode != null) { System.out.print(pnode.data+'-->'); pnode = pnode.next; } if(pnode == null) System.out.print('null'); } } //Main class to call linked list class functions and construct a linked list class Main{ public static void main(String() args) { /* create an empty list */ LinkedList lList = new LinkedList(); // Insert 40. lList.append(40); // Insert 20 at the beginning. lList.push(20); // Insert 10 at the beginning. lList.push(10); // Insert 50 at the end. lList.append(50); // Insert 30, after 20. lList.insertAfter(lList.head.next, 30); System.out.println('
Final linked list: '); lList. displayList (); } } 산출:
최종 연결 목록 :
10–> 20–> 30–> 40–> 50–> null
위의 프로그램, C ++ 및 Java 모두에서 목록 앞, 목록 끝 및 노드에 제공된 목록 사이에 노드를 추가하는 별도의 기능이 있습니다. 마지막으로 세 가지 방법을 모두 사용하여 만든 목록의 내용을 인쇄합니다.
# 2) 삭제
삽입과 마찬가지로 연결 목록에서 노드를 삭제하는 것은 노드를 삭제할 수있는 다양한 위치를 포함합니다. 연결 목록에서 첫 번째 노드, 마지막 노드 또는 임의의 k 번째 노드를 삭제할 수 있습니다. 삭제 후에는 연결 목록을 그대로 유지하기 위해 연결 목록의 다음 포인터와 다른 포인터를 적절하게 조정해야합니다.
다음 C ++ 구현에서는 두 가지 삭제 방법, 즉 목록에서 첫 번째 노드를 삭제하고 목록에서 마지막 노드를 삭제했습니다. 먼저 헤드에 노드를 추가하여 목록을 만듭니다. 그런 다음 삽입 및 삭제할 때마다 목록의 내용을 표시합니다.
#include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; //delete first node in the linked list Node* deleteFirstNode(struct Node* head) { if (head == NULL) return NULL; // Move the head pointer to the next node Node* tempNode = head; head = head->next; delete tempNode; return head; } //delete last node from linked list Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // first find second last node Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Delete the last node delete (second_last->next); // set next of second_last to null second_last->next = NULL; return head; } // create linked list by adding nodes at head void push(struct Node** head, int new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*head); (*head) = newNode; } // main function int main() { /* Start with the empty list */ Node* head = NULL; // create linked list push(&head, 2); push(&head, 4); push(&head, 6); push(&head, 8); push(&head, 10); Node* temp; cout<<'Linked list created ' 산출:
연결된 목록이 생성되었습니다.
10–> 8–> 6–> 4–> 2–
> NULL
헤드 노드 삭제 후 연결된 목록
8–> 6–> 4–> 2–
> NULL
마지막 노드 삭제 후 연결된 목록
8–> 6–> 4–> NULL
다음은 연결 목록에서 노드를 삭제하기위한 Java 구현입니다. 구현 로직은 C ++ 프로그램에서 사용되는 것과 동일합니다. 유일한 차이점은 연결된 목록이 클래스로 선언된다는 것입니다.
class Main { // Linked list node / static class Node { int data; Node next; }; // delete first node of linked list static Node deleteFirstNode(Node head) { if (head == null) return null; // Move the head pointer to the next node Node temp = head; head = head.next; return head; } // Delete the last node in linked list static Node deleteLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // search for second last node Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // set next of second last to null second_last.next = null; return head; } // Add nodes to the head and create linked list static Node push(Node head, int new_data) { Node newNode = new Node(); newNode.data = new_data; newNode.next = (head); (head) = newNode; return head; } //main function public static void main(String args()) { // Start with the empty list / Node head = null; //create linked list head = push(head, 1); head = push(head, 3); head = push(head, 5); head = push(head, 7); head = push(head, 9); Node temp; System.out.println('Linked list created :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteFirstNode(head); System.out.println('Linked list after deleting head node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteLastNode(head); System.out.println('Linked list after deleting last node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); } } 산출:
연결된 목록 생성 :
9–> 7–> 5–> 3–> 1–
> null
헤드 노드 삭제 후 연결된 목록 :
7–> 5–> 3–> 1–
> null
마지막 노드 삭제 후 연결된 목록 :
7–> 5–> 3–> null
노드 수 계산
연결 목록을 순회하면서 노드 수를 계산하는 작업을 수행 할 수 있습니다. 위의 구현에서 이미 노드를 삽입 / 삭제하거나 연결 목록의 내용을 표시해야 할 때마다 연결 목록을 처음부터 탐색해야한다는 것을 이미 살펴 보았습니다.
카운터를 유지하고 각 노드를 순회 할 때이를 증가 시키면 연결된 목록에있는 노드 수를 알 수 있습니다. 독자가 구현할 수 있도록이 프로그램을 남겨 둘 것입니다.
배열 및 연결 목록
연결 목록의 작동 및 구현을 살펴본 후 배열과 연결 목록이 서로 어떻게 공정한지 비교해 보겠습니다.
배열 연결된 목록 배열의 크기는 고정되어 있습니다. 연결된 목록 크기는 동적입니다. 새로운 요소의 삽입은 비싸다 삽입 / 삭제가 더 쉽습니다. 랜덤 액세스가 허용됩니다. 랜덤 액세스 불가 요소가 인접한 위치에 있습니다. 요소의 위치가 인접하지 않음 다음 포인터에 추가 공간이 필요하지 않습니다. 다음 포인터에 필요한 추가 메모리 공간
응용
배열과 연결 목록은 모두 항목을 저장하는 데 사용되며 선형 데이터 구조이므로 이러한 구조는 대부분의 응용 프로그램에서 유사한 방식으로 사용할 수 있습니다.
연결 목록의 일부 응용 프로그램은 다음과 같습니다.
- 연결 목록을 사용하여 스택 및 큐를 구현할 수 있습니다.
- 연결 목록은 그래프를 인접 목록으로 나타내야 할 때마다 그래프를 구현하는 데 사용할 수도 있습니다.
- 수학적 다항식을 연결 목록으로 저장할 수 있습니다.
- 해싱 기법의 경우 해싱에 사용되는 버킷은 연결 목록을 사용하여 구현됩니다.
- 프로그램에 동적 메모리 할당이 필요할 때마다 연결 목록이이 경우에 더 효율적으로 작동하므로 연결 목록을 사용할 수 있습니다.
결론
연결 목록은 데이터 항목을 선형 방식으로 저장하지만 인접하지 않은 위치에 저장하는 데 사용되는 데이터 구조입니다. 연결 목록은 데이터 부분을 포함하는 노드 모음과 목록에있는 다음 요소의 메모리 주소를 포함하는 다음 포인터입니다.
목록의 마지막 요소에는 다음 포인터가 NULL로 설정되어 있으므로 목록의 끝을 나타냅니다. 목록의 첫 번째 요소는 헤드입니다. 연결 목록은 삽입, 삭제, 순회 등과 같은 다양한 작업을 지원합니다. 동적 메모리 할당의 경우 연결 목록이 배열보다 선호됩니다.
연결된 목록은 배열과 같은 요소에 무작위로 액세스 할 수 없기 때문에 순회에 관한 한 비용이 많이 듭니다. 그러나 삽입-삭제 작업은 어레이와 비교할 때 비용이 적게 듭니다.
C ++ 트리 데이터 구조
이 자습서에서 선형 연결 목록에 대해 모두 배웠습니다. 연결된 목록은 순환 또는 이중 일 수도 있습니다. 다음 튜토리얼에서 이러한 목록에 대해 자세히 살펴볼 것입니다.
=> 완전한 C ++ 교육 시리즈는 여기에서 확인하십시오.
추천 도서