数据结构（四）--链表、双端链表、双向链表

一、链表

Node类和LinkList类。

二、双端链表

• 链表中保存着对最后一个链节点引用的链表。
• 从头部进行插入时，要对链表进行判断，如果为空要设置尾节点为新添加的节点。
• 从尾部进行插入时，如果链表为空，则直接设置头节点为新添加的节点，否则设置尾节点的后一个结点为新添加节点。
• 从头部进行删除时，判断头节点是否有下一个节点，如果没有则设置尾节点为null。
• 不可以从尾部进行删除，因为需要把尾节点的前一个节点的next置为null,但是没办法找到尾结点的前一个节点。
• 代码实现

  

  

  

  

三、双向链表

1. 双向链表   

   每个节点除了保存了对下一个节点的引用，同时还保存着对前一个节点的引用。

2.从头部插入

   对链表进行为空判断，若为空则设置尾节点为新添加的节点。如果不为空，则设置头节点的前一个节点为新添加的节点。

3.从尾部插入

    对链表进行为空判断，若为空则设置头节点为新添加的节点，否则设置尾节点的后一个节点为新添加节点。

4.从头部删除

   判断头节点是否有下一个节点，若没有则设置尾节点为null,否则设置头节点的下一个节点的previous为null。

5.从尾部删除

   若头节点后无其他节点，则设置头节点为null。否则设置尾结点前一个节点的next为null.设置尾节点为其前一个节点。

6.删除方法

  不需要再使用临时的指针域。

7.代码实现