Data Structures Algorithms 简明教程
Doubly Linked List Data Structure
What is Doubly Linked List?
双向链表是链表的一种变化形式，相较于单向链表，它可以用一种简单的方式实现向前和向后的导航。以下是理解双向链表概念的重要术语。
Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, forward as well as backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list.
-
Link − Each link of a linked list can store a data called an element.
-
Next − Each link of a linked list contains a link to the next link called Next.
-
Prev − Each link of a linked list contains a link to the previous link called Prev.
-
Linked List − A Linked List contains the connection link to the first link called First and to the last link called Last.
Doubly Linked List Representation
根据上述说明，以下是要考虑的重要事项。
As per the above illustration, following are the important points to be considered.
-
Doubly Linked List contains a link element called first and last.
-
Each link carries a data field(s) and a link field called next.
-
Each link is linked with its next link using its next link.
-
Each link is linked with its previous link using its previous link.
-
The last link carries a link as null to mark the end of the list.
Basic Operations in Doubly Linked List
以下是列表支持的基本操作。
Following are the basic operations supported by a list.
-
Insertion − Adds an element at the beginning of the list.
-
Insert Last − Adds an element at the end of the list.
-
Insert After − Adds an element after an item of the list.
-
Deletion − Deletes an element at the beginning of the list.
-
Delete Last − Deletes an element from the end of the list.
-
Delete − Deletes an element from the list using the key.
-
Display forward − Displays the complete list in a forward manner.
-
Display backward − Displays the complete list in a backward manner.
Doubly Linked List - Insertion at the Beginning
在此操作中，我们创建了一个包含三个区室的新节点，其中一个包含数据，另一个包含列表中其前一个和下一个节点的地址。这个新节点插入列表开头。
In this operation, we create a new node with three compartments, one containing the data, the others containing the address of its previous and next nodes in the list. This new node is inserted at the beginning of the list.
Algorithm
1. START
2. Create a new node with three variables: prev, data, next.
3. Store the new data in the data variable
4. If the list is empty, make the new node as head.
5. Otherwise, link the address of the existing first node to the
next variable of the new node, and assign null to the prev variable.
6. Point the head to the new node.
7. ENDDoubly Linked List - Insertion at the End
在此插入操作中，新输入节点将添加到双向链表的末尾；如果列表不为空。如果列表为空，则头指针将指向新节点。
In this insertion operation, the new input node is added at the end of the doubly linked list; if the list is not empty. The head will be pointed to the new node, if the list is empty.
Doubly Linked List - Deletion at the Beginning
此删除操作会删除双向链表中现有的第一个节点。头指针移到下一个节点，并移除链接。
This deletion operation deletes the existing first nodes in the doubly linked list. The head is shifted to the next node and the link is removed.