【数据结构和算法】双向链表

关于双向链表的介绍以及代码实现

---

1 双向链表

1.1 介绍

• 单向链表的对比：
• 单向链表查找的方向只能是一个方向，而双向链表可以向前或向后查找
• 单向链表不能自我删除，需要靠辅助接点，而双向链表则可以自我删除

1.2 思路

• （1）新增节点

• （2）删除节点

1.3 代码实现

• 双向链表的创建和单向链表的基本一致，只是部分对数据的修改方法要多写几步有所不同

• （1）代码

  public class DoubleLinkedList {
      //双向链表节点类
      private class DoubleNode {
          public DoubleNode pre; //前一个节点
          public Object data; //数据
          public DoubleNode next; //后一个节点
  
          public DoubleNode(Object data) {
              this.data = data;
          }
  
          @Override
          public String toString() {
              return "DoubleNode{ data = " + data + " }";
          }
      }
  
  
      private DoubleNode headNode; //头结点
  
      public DoubleLinkedList() {
          this.headNode = new DoubleNode(null);
      }
  
      /**
       * 添加数据（尾插）
       * @param data 数据
       */
      public void add(Object data) {
          DoubleNode temp = headNode;
  
          while(temp.next != null) {
              temp = temp.next;
          }
  
          //尾插
          DoubleNode newNode = new DoubleNode(data);
          temp.next = newNode;
          newNode.pre = temp;
      }
  
      /**
       * 插入数据（节点间插）
       * @param data 数据
       * @param index 下标
       */
      public void addByIndex(Object data, int index) {
          DoubleNode temp = headNode.next;
  
          //检验数据合法性
          if (index < 0 || index > getSize()) {
              System.out.println("error：Index越界，请重新去确认index大小！");
              return;
          }
  
          //index等于链表长度，直接尾插
          if(index == getSize()) {
              add(data);
              return;
          }
  
          int count = 0;
          while (count != index) {
              temp = temp.next;
              count ++;
          }
  
          //节点间插
          DoubleNode newNode = new DoubleNode(data);
          temp.pre.next = newNode;
          newNode.pre = temp.pre;
          newNode.next = temp;
          temp.pre = newNode;
      }
  
      /**
       * 修改数据
       * @param data 数据
       * @param index 下标
       */
      public void updateByIndex(Object data, int index) {
          DoubleNode temp = headNode.next;
  
          if(temp == null) {
              System.out.println("链表为空！");
              return;
          }
  
          //数据合法性校验
          if(index < 0 || index > getSize()-1) {
              System.out.println("error：Index数据不合法，请重新确认index的大小！");
              return;
          }
  
          int count = 0;
          while (count != index) {
              count ++;
              temp = temp.next;
          }
  		
  		//修改数据
          temp.data = data;
      }
  
      /**
       * 删除数据
       * @param index 下标
       */
      public void deleteByIndex(int index) {
          DoubleNode temp = headNode.next;
  
          //空链表判断
          if(temp == null) {
              System.out.println("error：链表为空！");
              return;
          }
  
          //数据合法校验
          if(index < 0 || index > getSize()-1) {
              System.out.println("error：index数据不合法，请重新确认Index的大小！");
              return;
          }
  
          int count = 0;
          while(count != index) {
              count ++;
              temp = temp.next;
          }
  
          //删除数据（注意删除最后一个数据引发空指针）
          temp.pre.next = temp.next;
          if(temp.next != null) {
              temp.next.pre = temp.pre;
          }
      }
  
      /**
       * 打印双向链表
       */
      public void print() {
          DoubleNode temp = headNode.next;
  
          if(temp == null) {
              System.out.println("链表为空！");
              return;
          }
  
          System.out.println("双向链表为：");
          int count = 0;
          while(temp != null) {
              System.out.print(count + " - ");
              System.out.println(temp);
              temp = temp.next;
              count ++;
          }
      }
  
      /**
       * 获取双向链表大小
       * @return int
       */
      public int getSize() {
          DoubleNode temp = headNode.next;
  
          if(temp.next == null) {
              return 0;
          }
  
          int count = 0;
          while(temp != null) {
              count ++;
              temp = temp.next;
          }
          return count;
      }
  }

• （2）测试

  @Test
  public void doubleLinkedListTest() {
  	//1.创建双向链表并插入数据
  	DoubleLinkedList linkedList = new DoubleLinkedList();
  	linkedList.add("hello");
  	linkedList.add("world");
  	linkedList.print();
  
  	//2. 节点间插入数据
  	linkedList.addByIndex("-", 1);
  	linkedList.print();
  
  	//3. 修改数据
  	linkedList.updateByIndex("!~!", 1);
  	linkedList.print();
  
  	//4. 删除数据
  	linkedList.deleteByIndex(1);
  	linkedList.print();
  }