Data Structures Algorithms 简明教程

Linked List Data Structure

What is Linked List?

链表是一种线性数据结构，可以通过链接（即指针）将一组“节点”存储在一起。链表节点没有存储在连续的位置，而是使用指向不同存储器位置的指针链接在一起。节点由数据值和指向链表内下一个节点的地址的指针组成。

链表是一种动态线性数据结构，其内存大小可以在运行时根据插入或删除操作分配或释放，这有助于有效地使用系统内存。链表可用于实现各种数据结构，如栈、队列、图、哈希映射等。

singly linked lists

链表从一个 head 节点开始，该节点指向第一个节点。每个节点包含一个数据，该数据包含与该节点关联的实际数据（值），以及指向链表中下一个节点的内存地址的下一个指针。最后一个节点称为列表中的尾节点，它指向 null ，表示列表的结束。

Linked Lists vs Arrays

对于数组，大小在创建时给出，因此数组是固定长度的，而链表大小是动态的，并且可以在链表中动态添加任意数量的节点。数组可以容纳相似类型的数据类型，而链表可以存储不同数据类型的大量节点。

Types of Linked List

以下为不同类型的链表。

Singly Linked Lists

单链表在一个节点中包含两个“存储段”；一个存储段存储数据，另一个存储段存储该列表下一个节点的地址。只能在一个方向中进行遍历，因为同一列表的两个节点之间只有一个链接。

singly linked lists

Doubly Linked Lists

双向链表在一个节点中包含三个“存储段”；一个存储段存储数据，另一个存储段存储该列表中前一个和下一个节点的地址。该列表被遍历两次，因为列表中的节点从两侧相互连接。

doubly linked lists

Circular Linked Lists

循环链表可存在于单向链表和双向链表。

由于循环链表中的最后一个节点与第一个节点相连接，因此对该链表中的遍历将一直继续，直到它被中断。

circular linked lists

Basic Operations in Linked List

链表中的基本操作包括插入、删除、搜索、显示以及删除指定关键处的元素。这些操作在单向链表中执行，如下所示：

  1. Insertion - 在列表开头添加一个元素。

  2. Deletion - 删除列表开头的一个元素。

  3. Display - 显示完整列表。

  4. Search - 使用指定的关键搜索元素。

  5. Delete - 使用指定的关键删除元素。

Linked List - Insertion Operation

在链表中添加一个新节点是多步活动。我们将在此处借助图表了解此内容。首先，使用相同结构创建一个节点，并找到要插入该节点的位置。

insertion operation

想象一下，我们在 A（LeftNode）和 C（RightNode）之间插入一个节点 B（NewNode）。然后将 B.next 指向 C -

NewNode.next -> RightNode;

它应该看起来像这样 -

inserting a node

现在，左侧的下一个节点应该指向新节点。

LeftNode.next -> NewNode;

这会将新节点放在两个节点中间。新列表应该看起来像这样 -

point to the new node

可以在链表中以三种不同的方式进行插入。解释如下：

Insertion at Beginning

在此操作中，我们在列表开头添加了一个元素。

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

以下是该操作在各种编程语言中的实现 −

Insertion at Ending

在此操作中，我们在列表结尾添加了一个元素。

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

以下是该操作在各种编程语言中的实现 −

Insertion at a Given Position

在此操作中，我们在列表中的任意位置添加了一个元素。

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

以下是该操作在各种编程语言中的实现 −

Linked List - Deletion Operation

删除也是一个多步过程。我们将以图片表示形式进行学习。首先，使用搜索算法找到要删除的目标节点。

deletion operation

现在，目标节点的左侧（前一个）节点应该指向目标节点的下一个节点 -

LeftNode.next -> TargetNode.next;
linked list deletion

这将删除指向目标节点的链接。现在，使用以下代码，我们将删除目标节点指向的内容。

TargetNode.next -> NULL;
pointing target node

我们需要使用已删除的节点。我们可以将它保留在内存中，否则我们可以简单地释放内存并完全擦除目标节点。

use deleted node
data items

如果节点被插入列表的开头，则应采取类似的步骤。在将其插入末尾时，列表的倒数第二个节点应指向新节点，并且新节点将指向 NULL。

链表中的删除也通过三种不同的方式执行。它们如下 -

Deletion at Beginning

在此链表的删除操作中，我们正在从列表的开头删除元素。为此，我们将头部指向第二个节点。

1. START
2. Assign the head pointer to the next node in the list
3. END

以下是该操作在各种编程语言中的实现 −

Deletion at Ending

在此链表的删除操作中，我们正在从列表的结尾删除元素。

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

以下是该操作在各种编程语言中的实现 −

Deletion at a Given Position

在此链表的删除操作中，我们正在从列表的任何位置删除元素。

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

以下是该操作在各种编程语言中的实现 −

Linked List - Reversal Operation

此操作是全面的。我们需要使最后一个节点由头节点指向并反转整个链表。

reverse operation

首先，我们遍历到列表的末尾。它应指向 NULL。现在，我们将其指向其前一个节点 -

traverse to the end

我们必须确保最后一个节点不是最后一个节点。因此，我们将拥有一个 temp 节点，它看起来像指向最后一个节点的头节点。现在，我们将使所有左侧节点逐一指向其前一个节点。

temp node

除了由头节点指向的节点（第一个节点），所有节点都应指向其前驱，使其成为其新的后继。第一个节点将指向 NULL。

point to null

我们将使头节点使用 temp 节点指向新的第一个节点。

the temp node

Algorithm

反转链表的分步过程如下 -

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.

Example

以下是该操作在各种编程语言中的实现 −

Linked List - Search Operation

使用键元素在列表中搜索元素。此操作与数组搜索相同；比较列表中的每个元素与给定的键元素。

Algorithm

1 START
2 If the list is not empty, iteratively check if the list
  contains the key
3 If the key element is not present in the list, unsuccessful
  search
4 END

Example

以下是该操作在各种编程语言中的实现 −

Linked List - Traversal Operation

遍历操作按顺序遍历列表中的所有元素，并按该顺序显示元素。

Algorithm

1. START
2. While the list is not empty and did not reach the end of the list,
   print the data in each node
3. END

Example

以下是该操作在各种编程语言中的实现 −

Linked List - Complete implementation

以下是各种编程语言中链表的完整实现：