目录
1.什么是双向链表？
2.双向链表的基本功能和结构
3.双向链表基本功能详细图解代码实现
1.清空，判空，获得长度功能实现
2.获取第一个元素和最后一个元素
3.添加元素t
4.向指定位置i插入元素t
5.获取指定位置i处的元素
6.找到元素t第一次出现的位置
7.删除位置i的元素，并返回该元素
要明白什么是双向链表，我们首先得明白什么是链表和什么是单链表？如果对于这个还有疑惑的推荐我的这篇博客，里面有非常详细的图解和代码实现。
首先我们通过一张直观的图对比单链表和双向链表
通过名字我们就可知它之所以叫双向链表，就是它可以向两头遍历，任意一个结点我可以得到它的前结点和后一个结点。不像单链表具有单向遍历的局限性，而且双向链表同时记录了尾结点last，这样我们每次想得到最后一个结点就不需要从头遍历到末尾了，如果链表很长的话，这样每次循环查询是非常浪费时间的。
解析：学习数据结构，我们在学习它的基本功能前，一定要明白它的逻辑结构。代码中，首先有一个内部类Node表示为结点，因为一个结点具有指针域和数据域，所以需要用一个类来表示，Node里面首先有表示存放数据的item，因为不清楚存放的数据是什么类型，所以用泛型T表示。同时有两个Node类型的变量pre和next分别记录指向前一个结点和后一个结点。在链表中有两个个Node类型的变量head和last分别表示头指针和尾指针，同时有一个int类型的N记录成员个数。初始化时，只需要建立头结点和尾结点，内部属性都为null，再让N为0即可。
public void clear()
清空链表
public int getLength()
获取链表长度
public boolean isEmpty()
判断链表是否为空
public T getFirst()
获取第一个元素
public T getLast()
获取最后一个元素
public void add(T t)
插入元素t
public void insert(int i,T t)
向指定位置i位置插入元素t
public T get(int i)
获取指定位置i处的元素
public int indexOf(T t)
public T remove(int i)
找到元素t第一次出现的位置
删除位置i处的元素,并返回该元素
看上去很多API功能需要实现，但其实大部分都很简单，只要理解就可以自己写出来。
解析：这里我需要提醒大家，虽然头结点我们一般不存储元素，但是尾结点我们是可以存储的元素的，不要硬性思维。清空时，我们需要让头结点的next为null，这样无法从头进入链表，尾结点因为也是存储数据的，所以得直接让last为null，同时让N为0。获得链表长度直接返回N。判空也是直接返回N是否等于0的值即可。
解析：无论是获取哪个，我们都需要获取判空操作，养成好习惯，代码一定要考虑进所有情况，否则容易出异常。因为是获取元素，所以我们返回的一定是某个结点的item，第一个元素，说明就是头结点的next的item，最后一个元素就是返回last的item就好。
解析：同样我们需要对链表进行判空操作，如果链表为空，我们需要new一个新节点存入数据t，因为就它一个结点，所以我们把它赋值给last，让它成为尾结点，然后让head指向它即可。如果链表不为空，我们首先需要用一个结点oldLast记录旧的尾结点，同时new一个新节点放入数据t，让它成为新的尾结点last，同时让旧的尾结点oldLast指向它。最后无论怎样都记得让N++。
具体的步骤通过下图就能明白，一定要搞清楚每一步的顺序，否则很容易出错，自己可以草稿画图模拟。
解析：和单链表相同，从头结点开始遍历打i处，返回item即可。
解析：单单链表一致，从头结点开始遍历，同时判断是否是查找的元素，如果找到返回位置i，否则循环结束后返回-1。
如下图解即可明白，主要是要分清步骤，不要搞混，返回的是值不是结点。
总结：双向链表与单链表虽然有所区别，但方法的实现大同小异，我们也应该熟练掌握，多画图更易帮助我们理解，都是基础的知识。
有错的地方还望在评论区提出，水平有限
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/13680.html