Data Structures Algorithms 简明教程
Linked List Data Structure
What is Linked List?
链表是一种线性数据结构，可以通过链接（即指针）将一组“节点”存储在一起。链表节点没有存储在连续的位置，而是使用指向不同存储器位置的指针链接在一起。节点由数据值和指向链表内下一个节点的地址的指针组成。
A linked list is a linear data structure which can store a collection of "nodes" connected together via links i.e. pointers. Linked lists nodes are not stored at a contiguous location, rather they are linked using pointers to the different memory locations. A node consists of the data value and a pointer to the address of the next node within the linked list.
链表是一种动态线性数据结构，其内存大小可以在运行时根据插入或删除操作分配或释放，这有助于有效地使用系统内存。链表可用于实现各种数据结构，如栈、队列、图、哈希映射等。
A linked list is a dynamic linear data structure whose memory size can be allocated or de-allocated at run time based on the operation insertion or deletion, this helps in using system memory efficiently. Linked lists can be used to implment various data structures like a stack, queue, graph, hash maps, etc.
链表从一个 head 节点开始，该节点指向第一个节点。每个节点包含一个数据，该数据包含与该节点关联的实际数据（值），以及指向链表中下一个节点的内存地址的下一个指针。最后一个节点称为列表中的尾节点，它指向 null ，表示列表的结束。
A linked list starts with a head node which points to the first node. Every node consists of data which holds the actual data (value) associated with the node and a next pointer which holds the memory address of the next node in the linked list. The last node is called the tail node in the list which points to null indicating the end of the list.
Linked Lists vs Arrays
对于数组，大小在创建时给出，因此数组是固定长度的，而链表大小是动态的，并且可以在链表中动态添加任意数量的节点。数组可以容纳相似类型的数据类型，而链表可以存储不同数据类型的大量节点。
In case of arrays, the size is given at the time of creation and so arrays are of fixed lenghth where as Linked lists are dynamic in size and any number of nodes can be added in the linked lists dynamically. An array can accommodate similar types of data types where as linked lists can store various nodes of different data types.
Types of Linked List
以下为不同类型的链表。
Following are the various types of linked list.
Singly Linked Lists
单链表在一个节点中包含两个“存储段”；一个存储段存储数据，另一个存储段存储该列表下一个节点的地址。只能在一个方向中进行遍历，因为同一列表的两个节点之间只有一个链接。
Singly linked lists contain two "buckets" in one node; one bucket holds the data and the other bucket holds the address of the next node of the list. Traversals can be done in one direction only as there is only a single link between two nodes of the same list.
Doubly Linked Lists
双向链表在一个节点中包含三个“存储段”；一个存储段存储数据，另一个存储段存储该列表中前一个和下一个节点的地址。该列表被遍历两次，因为列表中的节点从两侧相互连接。
Doubly Linked Lists contain three "buckets" in one node; one bucket holds the data and the other buckets hold the addresses of the previous and next nodes in the list. The list is traversed twice as the nodes in the list are connected to each other from both sides.
Circular Linked Lists
循环链表可存在于单向链表和双向链表。
Circular linked lists can exist in both singly linked list and doubly linked list.
由于循环链表中的最后一个节点与第一个节点相连接，因此对该链表中的遍历将一直继续，直到它被中断。
Since the last node and the first node of the circular linked list are connected, the traversal in this linked list will go on forever until it is broken.
Basic Operations in Linked List
链表中的基本操作包括插入、删除、搜索、显示以及删除指定关键处的元素。这些操作在单向链表中执行，如下所示：
The basic operations in the linked lists are insertion, deletion, searching, display, and deleting an element at a given key. These operations are performed on Singly Linked Lists as given below −
-
Insertion − Adds an element at the beginning of the list.
-
Deletion − Deletes an element at the beginning of the list.
-
Display − Displays the complete list.
-
Search − Searches an element using the given key.
-
Delete − Deletes an element using the given key.
Linked List - Insertion Operation
在链表中添加一个新节点是多步活动。我们将在此处借助图表了解此内容。首先，使用相同结构创建一个节点，并找到要插入该节点的位置。
Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams here. First, create a node using the same structure and find the location where it has to be inserted.
想象一下，我们在 A（LeftNode）和 C（RightNode）之间插入一个节点 B（NewNode）。然后将 B.next 指向 C -
Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then point B.next to C −
NewNode.next -> RightNode;它应该看起来像这样 -
It should look like this −
现在，左侧的下一个节点应该指向新节点。
Now, the next node at the left should point to the new node.
LeftNode.next -> NewNode;这会将新节点放在两个节点中间。新列表应该看起来像这样 -
This will put the new node in the middle of the two. The new list should look like this −
可以在链表中以三种不同的方式进行插入。解释如下：
Insertion in linked list can be done in three different ways. They are explained as follows −
Insertion at Beginning
在此操作中，我们在列表开头添加了一个元素。
In this operation, we are adding an element at the beginning of the list.
1. START
2. Create a node to store the data
3. Check if the list is empty
4. If the list is empty, add the data to the node and
assign the head pointer to it.
5. If the list is not empty, add the data to a node and link to the
current head. Assign the head to the newly added node.
6. END以下是该操作在各种编程语言中的实现 −
Following are the implementations of this operation in various programming languages −
Insertion at Ending
在此操作中，我们在列表结尾添加了一个元素。
In this operation, we are adding an element at the ending of the list.
1. START
2. Create a new node and assign the data
3. Find the last node
4. Point the last node to new node
5. END以下是该操作在各种编程语言中的实现 −
Following are the implementations of this operation in various programming languages −
Insertion at a Given Position
在此操作中，我们在列表中的任意位置添加了一个元素。
In this operation, we are adding an element at any position within the list.
1. START
2. Create a new node and assign data to it
3. Iterate until the node at position is found
4. Point first to new first node
5. END以下是该操作在各种编程语言中的实现 −
Following are the implementations of this operation in various programming languages −
Linked List - Deletion Operation
删除也是一个多步过程。我们将以图片表示形式进行学习。首先，使用搜索算法找到要删除的目标节点。
Deletion is also a more than one step process. We shall learn with pictorial representation. First, locate the target node to be removed, by using searching algorithms.
现在，目标节点的左侧（前一个）节点应该指向目标节点的下一个节点 -
The left (previous) node of the target node now should point to the next node of the target node −
LeftNode.next -> TargetNode.next;
这将删除指向目标节点的链接。现在，使用以下代码，我们将删除目标节点指向的内容。
This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at.
TargetNode.next -> NULL;
我们需要使用已删除的节点。我们可以将它保留在内存中，否则我们可以简单地释放内存并完全擦除目标节点。
We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate memory and wipe off the target node completely.
如果节点被插入列表的开头，则应采取类似的步骤。在将其插入末尾时，列表的倒数第二个节点应指向新节点，并且新节点将指向 NULL。
Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at the end, the second last node of the list should point to the new node and the new node will point to NULL.
链表中的删除也通过三种不同的方式执行。它们如下 -
Deletion in linked lists is also performed in three different ways. They are as follows −
Deletion at Beginning
在此链表的删除操作中，我们正在从列表的开头删除元素。为此，我们将头部指向第二个节点。
In this deletion operation of the linked, we are deleting an element from the beginning of the list. For this, we point the head to the second node.
1. START
2. Assign the head pointer to the next node in the list
3. END以下是该操作在各种编程语言中的实现 −
Following are the implementations of this operation in various programming languages −
Deletion at Ending
在此链表的删除操作中，我们正在从列表的结尾删除元素。
In this deletion operation of the linked, we are deleting an element from the ending of the list.
1. START
2. Iterate until you find the second last element in the list.
3. Assign NULL to the second last element in the list.
4. END以下是该操作在各种编程语言中的实现 −
Following are the implementations of this operation in various programming languages −
Deletion at a Given Position
在此链表的删除操作中，我们正在从列表的任何位置删除元素。
In this deletion operation of the linked, we are deleting an element at any position of the list.
1. START
2. Iterate until find the current node at position in the list.
3. Assign the adjacent node of current node in the list
to its previous node.
4. END以下是该操作在各种编程语言中的实现 −
Following are the implementations of this operation in various programming languages −
Linked List - Reversal Operation
此操作是全面的。我们需要使最后一个节点由头节点指向并反转整个链表。
This operation is a thorough one. We need to make the last node to be pointed by the head node and reverse the whole linked list.
首先，我们遍历到列表的末尾。它应指向 NULL。现在，我们将其指向其前一个节点 -
First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to its previous node −
我们必须确保最后一个节点不是最后一个节点。因此，我们将拥有一个 temp 节点，它看起来像指向最后一个节点的头节点。现在，我们将使所有左侧节点逐一指向其前一个节点。
We have to make sure that the last node is not the last node. So we’ll have some temp node, which looks like the head node pointing to the last node. Now, we shall make all left side nodes point to their previous nodes one by one.
除了由头节点指向的节点（第一个节点），所有节点都应指向其前驱，使其成为其新的后继。第一个节点将指向 NULL。
Except the node (first node) pointed by the head node, all nodes should point to their predecessor, making them their new successor. The first node will point to NULL.
我们将使头节点使用 temp 节点指向新的第一个节点。
We’ll make the head node point to the new first node by using the temp node.
Algorithm
反转链表的分步过程如下 -
Step by step process to reverse a linked list is as follows −
1. START
2. We use three pointers to perform the reversing:
prev, next, head.
3. Point the current node to head and assign its next value to
the prev node.
4. Iteratively repeat the step 3 for all the nodes in the list.
5. Assign head to the prev node.Linked List - Search Operation
使用键元素在列表中搜索元素。此操作与数组搜索相同；比较列表中的每个元素与给定的键元素。
Searching for an element in the list using a key element. This operation is done in the same way as array search; comparing every element in the list with the key element given.
Linked List - Traversal Operation
遍历操作按顺序遍历列表中的所有元素，并按该顺序显示元素。
The traversal operation walks through all the elements of the list in an order and displays the elements in that order.