Doubly Linked List
     
insert before    insert after
   Step-by-Step Animation   Animation Speed 
Elaboration:
?
Doubly Linked List: This is a circular linked list structure with a sentinel node. The sentinel node is an additional node. It does not store any data. It helps to find the first and last node on the list.
Node: It has three fields. Its information is shown in a rectangle. The label below the rectangle shows the associated memory address
(1) The value field: It stores the data. The type of data is determined by the problem.
(2) The forward link: It stores the pointer to the next node.
(3) The backward link: It stores the pointer to the previous node.
API Explanation:
1. Push Back: Add a new node at the end - O(1)
2. Pop Back: Remove the last node - O(1)
3. Push Front: Add a new node at the beginning - O(1)
4. Pop Front: Remove the first node - O(1)
5. Erase: Erase a node given its memory address - O(1)
6. Insert Before: Insert a new node before the given node - O(1)
7. Insert After: Insert a new node after the given node - O(1)
8. Clear List: Clear the entire list
双向链表定义: 双向链表是一种特殊的链表,其节点包括三个部分:前驱指针域、数据域和后继指针域。
(1)数据域(data),用于存储该结点的数据元素,数据元素类型由应用问题决定。
(2)后继指针域,又称为右链指针,用于存放一个指针,该指针指向下一个结点的开始存储地址。
(3)前驱指针域,又称为左链指针,用于存放一个指针,该指针指向上一个结点的开始存储地址。
Node:节点图像框中的第一层为节点中的数据值,第二层为节点中的后继指针域(它存储着下一个节点的存储地址),第三层为节点中的前驱指针域(它存储着上一个节点的存储地址)。
按键说明:
1. Push Back & Pop Back :在输入框内输入要添加的节点的数据值,点击” Push Back”将节点从最右侧插入(注意:这个节点其实是作为哨兵节点的前置节点进行插入的)。点击”Pop Back”则默认从最右侧弹出一个节点(弹出节点与用户的输入值无关)。
2. Push Front & Pop Front: 在输入框内输入要添加的节点的数据值,点击” Push Front”将节点从最左侧插入(注意:这个节点其实是作为哨兵节点的后置节点进行插入的)。点击”Pop Front”则默认从最左侧弹出一个节点(弹出节点与用户的输入值无关)。
3. Erase: 请在输入框中输入要删除节点的存储地址。
4. Clear List: 清除创建的整个列表。
5. Insert Before(靠左): 请在”insert”后的输入框中输入要添加节点的数据值,接着在”before”后的输入框中输入一个列表中现有节点的地址,便可以将一个新的节点作为前置节点插入到所选择的现有节点前。
6. Insert After(靠右):请在”insert”后的输入框中输入要添加节点的数据值,接着在”after”后的输入框中输入一个列表中现有节点的地址,便可以将一个新的节点作为后置节点插入到所选择的现有节点后。