ㅏ 연결리스트 데이터 요소를 저장하는 데 사용하는 일종의 선형 동적 데이터 구조입니다. 배열은 데이터 항목이 연속적인 메모리 블록에 저장되는 일종의 선형 데이터 구조이기도 합니다.
배열과 달리 연결된 목록은 인접한 메모리 영역이나 블록에 데이터 요소를 저장할 필요가 없습니다.
인터넷을 사용하여
ㅏ 연결리스트 두 부분으로 나누어진 '노드'라는 요소로 구성됩니다. 첫 번째 컴포넌트는 실제 데이터를 저장하는 부분이고, 두 번째 컴포넌트는 다음 노드에 대한 포인터를 저장하는 부분입니다. 이러한 유형의 구조를 ''이라고 합니다. 단일 연결 리스트 .'
C++의 연결리스트
이 튜토리얼에서는 단일 연결 목록을 자세히 살펴보겠습니다.
단일 연결 리스트의 구조는 아래 다이어그램에 설명되어 있습니다.
- 위 부분에서 보았듯이 연결리스트의 첫 번째 노드를 '헤드'라고 하고, 마지막 노드를 '테일'이라고 합니다. 마지막 노드에 메모리 주소가 지정되지 않았기 때문에 연결 리스트의 마지막 노드에는 null 다음 포인터가 있습니다.
- 각 노드에는 다음 노드에 대한 포인터가 포함되어 있으므로 연결 목록의 데이터 요소는 연속 위치에 유지될 필요가 없습니다. 노드는 메모리 전체에 분산될 수 있습니다. 각 노드에는 그 다음 노드의 주소가 있으므로 원할 때마다 노드에 액세스할 수 있습니다.
- 연결된 목록에서 데이터 항목을 빠르게 추가하고 제거할 수 있습니다. 결과적으로 연결된 목록은 동적으로 증가하거나 축소될 수 있습니다. 연결된 목록에는 포함할 수 있는 데이터 항목의 최대량이 없습니다. 결과적으로, 사용 가능한 RAM이 있는 한 연결 목록에 원하는 만큼 많은 데이터 항목을 추가할 수 있습니다.
- 연결된 목록에 필요한 항목 수를 미리 지정할 필요가 없기 때문에 연결 목록은 삽입 및 삭제가 간편할 뿐만 아니라 메모리 공간도 절약됩니다. 연결리스트가 사용하는 유일한 공간은 다음 노드에 대한 포인터를 저장하는 것인데, 이로 인해 약간의 비용이 추가됩니다.
그 다음에는 연결된 목록에서 수행할 수 있는 다양한 작업을 살펴보겠습니다.
1) 삽입
연결된 목록은 추가 작업으로 확장됩니다. 간단해 보이지만 연결된 목록의 구조를 보면 데이터 항목이 추가될 때마다 추가한 새 항목의 이전 노드와 다음 노드의 다음 포인터를 변경해야 한다는 것을 알고 있습니다.
새 데이터 항목이 삽입될 위치는 두 번째로 고려해야 할 측면입니다.
연결된 목록에 데이터 항목을 추가할 수 있는 위치는 세 군데입니다.
리눅스 폴더 이름 바꾸기
ㅏ. 연결리스트로 시작하기
아래는 2->4->6->8->10의 숫자가 연결된 목록입니다. 노드 2를 가리키는 헤드는 이제 노드 1을 가리키고, 목록의 첫 번째 노드로 새 노드 1을 추가하면 아래 그림과 같이 노드 1의 다음 포인터는 노드 2의 메모리 주소를 갖게 됩니다. .
결과적으로 새로운 연결리스트는 1->2->4->6->8->10이 됩니다.
비. 주어진 노드 이후
이 경우 노드가 제공되며 그 뒤에 새 노드를 추가해야 합니다. 연결리스트 a->b->c->d->e에 노드 c 다음에 노드 f를 추가하면 연결리스트는 다음과 같이 보입니다.
따라서 지정된 노드가 위 다이어그램에 있는지 확인합니다. 존재하는 경우 새 노드 f가 생성됩니다. 그 후, 우리는 새로운 노드 f에서 노드 c의 다음 포인터를 가리킵니다. 노드 f의 다음 포인터는 이제 노드 d를 가리킵니다.
씨. 연결리스트의 마지막 항목
세 번째 경우에는 연결된 목록의 끝에 새 노드가 추가됩니다. 아래 링크된 목록을 고려하세요: a->b->c->d->e, 끝에 노드 f가 추가됩니다. 노드를 추가하면 다음과 같은 연결리스트가 나타납니다.
결과적으로 우리는 새로운 노드 f를 구성합니다. 널로 이어지는 꼬리 포인터는 f를 가리키고 노드 f의 다음 포인터는 널을 가리킵니다. 아래 프로그래밍 언어에서는 세 가지 유형의 삽입 기능을 모두 생성했습니다.
연결된 목록은 C++의 구조 또는 클래스로 선언될 수 있습니다. 구조로 선언된 연결 목록은 고전적인 C 스타일 문입니다. 연결된 목록은 주로 표준 템플릿 라이브러리를 사용할 때 최신 C++에서 클래스로 사용됩니다.
다음 애플리케이션에서는 연결 목록을 선언하고 생성하기 위해 구조가 사용되었습니다. 해당 멤버는 데이터와 다음 요소에 대한 포인터입니다.
C++ 프로그램:
#include using namespace std; struct Node { int data; struct Node *next; }; void push ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; newNode1 -> data = nodeData; newNode1 -> next = (*head); (*head) = newNode1; } void insertAfter ( struct Node* prevNode, int nodeData ) { if ( prevNode == NULL ) { cout <data = nodedata; newnode1 -> next = prevNode -> next; prevNode -> next = newNode1; } void append ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; struct Node *last = *head; newNode1 -> data = nodeData; newNode1 -> next = NULL; if ( *head == NULL ) { *head = newNode1; return; } while ( last -> next != NULL ) last = last -> next; last -> next = newNode1; return; } void displayList ( struct Node *node ) { while ( node != NULL ) { cout <data <'; node="node" -> next; } if ( node== NULL) cout<next, 55 ); cout << 'final linked list: ' endl; displaylist (head); return 0; } < pre> <p> <strong>Output:</strong> </p> <pre> Final linked list: 35-->25-->55-->15-->45-->null </pre> <h3>2) Deletion</h3> <p>Similar to insertion, deleting a node from a linked list requires many points from which the node might be eliminated. We can remove the linked list's first, last, or kth node at random. We must correctly update the next pointer and all other linked list pointers in order to maintain the linked list after deletion.</p> <p>In the following C++ implementation, we have two deletion methods: deleting the list's initial node and deleting the list's last node. We begin by adding nodes to the head of the list. The list's contents are then shown following each addition and deletion.</p> <p> <strong>C++ Program:</strong> </p> <pre> #include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <'; if ( temp="=" null ) cout << 'null' endl; head="deletingFirstNode" (head); 'linked list after deleting node' < next <data cout<<'null'<<endl; last data 'null'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data></pre></next,></data></data> 2) 삭제
삽입과 유사하게 연결 목록에서 노드를 삭제하려면 노드가 제거될 수 있는 많은 지점이 필요합니다. 연결리스트의 첫 번째, 마지막, k번째 노드를 무작위로 제거할 수 있습니다. 삭제 후에도 연결된 목록을 유지하려면 다음 포인터와 다른 모든 연결된 목록 포인터를 올바르게 업데이트해야 합니다.
다음 C++ 구현에는 목록의 초기 노드 삭제와 목록의 마지막 노드 삭제라는 두 가지 삭제 방법이 있습니다. 목록의 헤드에 노드를 추가하는 것부터 시작합니다. 그러면 각 추가 및 삭제 후에 목록의 내용이 표시됩니다.
csv 자바에서 읽기
C++ 프로그램:
#include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <\'; if ( temp="=" null ) cout << \'null\' endl; head="deletingFirstNode" (head); \'linked list after deleting node\' < next <data cout<<\'null\'<<endl; last data \'null\'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data> 노드 수
연결리스트를 순회하면서 노드 수를 세는 과정을 수행할 수 있다. 이전 접근 방식에서는 노드를 삽입/삭제하거나 연결 목록의 내용을 표시해야 하는 경우 처음부터 연결 목록을 순회해야 한다는 것을 알았습니다.
카운터를 설정하고 증가시키면서 각 노드를 순회하면 연결된 목록의 노드 수가 제공됩니다.
배열과 연결 목록의 차이점:
| 정렬 | 연결리스트 |
|---|---|
| 배열에는 정의된 크기가 있습니다. | 연결리스트의 크기는 가변적입니다. |
| 새로운 요소를 삽입하는 것은 어렵습니다. | 삽입과 삭제가 더 간단해졌습니다. |
| 무작위로 접근이 허용됩니다. | 임의 접근은 불가능합니다. |
| 요소가 상대적으로 가깝거나 연속되어 있습니다. | 요소가 연속되어 있지 않습니다. |
| 다음 포인터에는 추가 공간이 필요하지 않습니다. | 다음 포인터에는 추가 메모리가 필요합니다. |
기능성
연결된 목록과 배열은 모두 객체를 보유하는 선형 데이터 구조이므로 대부분의 응용 프로그램에서 비슷한 방식으로 활용될 수 있습니다.
다음은 연결된 목록 응용 프로그램의 몇 가지 예입니다.
자바는 다음을 가지고
- 스택과 큐는 연결된 목록을 사용하여 구현할 수 있습니다.
- 그래프를 인접 목록으로 표현해야 할 경우 연결 목록을 사용하여 구현할 수 있습니다.
- 연결 리스트를 사용하여 수학적 다항식을 포함할 수도 있습니다.
- 해싱의 경우 버킷을 구현하기 위해 연결된 목록이 사용됩니다.
- 프로그램에 동적 메모리 할당이 필요한 경우 연결 목록이 더 효율적이므로 연결 목록을 활용할 수 있습니다.
결론
연결 목록은 선형이지만 연속되지 않은 형식으로 데이터 요소를 보유하는 데 사용되는 데이터 구조입니다. 연결된 목록은 각각 두 개의 구성 요소가 있는 노드로 구성됩니다. 첫 번째 구성 요소는 데이터로 구성되고, 두 번째 구성 요소에는 목록의 다음 구성원의 메모리 주소를 저장하는 포인터가 있습니다.
연결된 목록이 끝났다는 표시로 목록의 마지막 항목에는 다음 포인터가 NULL로 설정됩니다. 머리는 목록의 첫 번째 항목입니다. 연결된 목록을 사용하면 삽입, 삭제, 순회 등과 같은 다양한 작업이 가능합니다. 동적 메모리 할당에는 배열보다 연결 목록이 선호됩니다.
연결 목록은 배열처럼 요소에 무작위로 액세스할 수 없기 때문에 인쇄하거나 탐색하기 어렵습니다. 배열과 비교할 때 삽입-삭제 절차는 비용이 더 저렴합니다.
이 튜토리얼에서는 선형 연결 목록에 대해 알아야 할 모든 것을 배웠습니다. 연결된 목록은 이중으로 연결되거나 순환될 수도 있습니다. 다음 자습서에서는 이러한 목록을 자세히 살펴보겠습니다.