双向链表的定义及基本操作

        在“匠人的算法课I”中我们详细介绍了单链表的创建、插入结点、删除结点等基本操作。单链表的优点是插入结点和删除结点的时间复杂度较低，不需要像数组那样批量移动数据，但是单链表也存在着明显的不足，那就是每次定位一个结点都需要从单链表的头部开始向后遍历，而且遍历的方向永远是单向的（从前往后）。这就导致如果不知道要插入或删除的结点的前一个结点的指针，就需要从链表头开始向后遍历链表，因此时间复杂度仍为O(n)，这样链表相较于数组的优势就不明显了。所以在实际应用中，人们更常使用的是改进的链表结构，例如循环链表，双向链表或者是双向循环链表。本讲我们来介绍双向链表。

        顾名思义双向链表就是指针朝前后两个方向都能自由移动的链表，这是双向链表与单链表最本质的区别。为了实现指针可以朝前后两个方向自由移动，在链表结点中需要设置两个指针，一个指针指向后继结点，一个指针指向前驱结点。如图1所示。

图1 双向链表的结构

        从图1可以看出，双向链表与单链表的根本区别就在于每个结点中多出了一个指向前驱结点的指针域，通过这个指针域中保存的地址就可以方便地访问到该结点的前驱结点，从而使得访问结点更加灵活方便。

双向链表的定义

        双向链表是由链表结点构成的，因此在定义双向链表之前首先要定义双向链表的结点。

class Node {int data;Node next;Node prev;public Node(int data) {this.data = data;next = null;prev = null;}
}

        在Node类中包含3个成员变量：data为整型变量，它是该结点中的数据域，可用来存放一个整数；next是Node类型的变量（引用类型变量），next中保存该结点后继结点的指针；prev也是Node类型的变量（引用类型变量），prev中保存该结点前驱结点的指针。

        接下来可以定义双向链表类。

public class MyDoubleLinkedList {Node head;int length;public boolean insertNode(int data, int index) {//在双向链表的index位置上插入一个结点，结点中的数据为data}public boolean deleteNode(int index) {//删除双向链表中index位置上的结点}
}

    MyDoubleLinkedList是我们定义的双向链表类，该类包含两个成员变量：head是Node类型的成员，它是这个双向链表的头指针，用来指向双向链表的第一个结点；length是一个整型变量，用来记录双向链表中结点的个数。同时在MyDoubleLinkedList类中还定义了两个成员方法用来对双向链表进行操作。方法insertNode(int data, int index)的作用是在双向链表的index位置上插入一个结点，结点中的数据为data。方法deleteNode(int index)的作用是删除双向链表中index位置上的结点。
双向链表的操作

        最基本的操作包括向双向链表中插入结点，从双向链表中删除结点。除此之外，还可以根据需要定义其他的操作方法。在这里主要介绍插入结点和删除结点的方法，这两个方法中包含了双向链表的最基本操作，所以最具有代表性。

向双向链表中插入结点

        前面已经给出了向双向链表中插入结点方法的定义，如下：

public boolean insertNode(int data, int index)

        该方法的作用是在双向链表的index位置上插入一个元素为整型变量data的结点。这里需要声明，所谓在双向链表的index位置上插入结点是指新插入的结点最终将位于链表的第index位置上，index是从1开始计算的。例如在一个包含3个结点的双向链表的第3个位置上插入结点，最终该双向链表的形态如图2所示。

图2 向双向链表的第3个位置上插入结点

        很显然，如果链表的长度为length，那么插入一个结点后其长度将变为length+1。因此新插入的结点只能位于链表的1（包含）到length+1（包含）的位置上，所以index的取值范围只能是从1（包含）到length+1（包含）之间的值，不在这个范围内的index值都是非法的。

        如何在双向链表的第index位置上插入结点呢？有的同学可能会被双向链表结点中的prev和next指针搞晕，其实只要按照下面的步骤进行，是很容易完成这个操作的。

        （1）首先通过一个循环操作找到要插入位置的前一个结点，并用指针curNode指向这个结点。例如要想在包含3个结点的双向链表中的第3个位置上插入结点，就要将curNode指向该双向链表的第2个结点。如图3所示。

图3 将curNode指向第二个结点

        （2）创建一个新的结点，然后用指针node指向该结点。如图4所示。

图4 创建新的结点并用node指向该结点

        （3）修改4个指针域实现结点的插入：curNode.next.prev，node.next，node.prev，curNode.next。如图5所示。

图5 向双向链表中插入结点（修改4个指针域的内容）

        需要注意的是，当插入的新结点位于双向链表的第一个位置（index=1）或者最后一个位置（index=length+1）时需要做特殊处理，此时需要修改的指针域要少一些，大家可结合代码自行研究。

        下面给出向双向链表的index位置上插入结点的Java代码实现。

 public boolean insertNode(int data, int index) {if (index < 1 || index > ( length + 1 )) {//插入结点的位置非法，直接返回falseSystem.out.println("insert node fail");return false;}if (index == 1) {//在第一个位置插入结点if (head == null) {//此时链表中没有结点head = new Node(data);} else {Node node = new Node(data);head.prev = node;node.next = head;head = node;}} else {Node curNode = head;for (int i=1; i

public boolean deleteNode(int index)

  public boolean deleteNode(int index) {if (index<1 || index > length) {System.out.println("delete node fail");return false;}if (index == 1) {head = head.next;head.prev.next=null;head.prev = null;length--;return true;}Node curNode = head;for (int i=1; i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！