双向链表（Doubly Linked List）是一种常见的数据结构，它在链表的基础上增加了一个指向前一个节点的指针，这使得在双向链表中可以方便地进行双向遍历。
创建双向链表的步骤：
定义节点类：首先，定义一个节点类，这个节点类通常包含三个属性：数据域（存储数据的部分）、指向下一个节点的指针（通常称为next或forward），以及指向前一个节点的指针（通常称为prev或backward）。
//定义一个节点类 public class Node { //数据域 int data; //指向下一个节点的指针 Node next; //指向前一个节点的指针 Node prev; public Node(int data) { this.data=data; this.next=null; this.prev=null; } }
创建链表：创建一个链表对象，通常包括一个指向链表头部和尾部的指针。该类包含链表的操作方法，如添加节点、删除节点等。
public class DoublyLinkedList { //创建一个链表对象，通常包括一个指向链表头部和尾部的指针 private Node head; private Node tail; public DoublyLinkedList() { this.head=null; this.tail=null; } //添加节点 public void append(int data) { Node newNode=new Node(data); if (tail==null) { head=newNode; tail=newNode; }else { //更新 prev 和 next 指针 tail.next=newNode; newNode.prev=tail; tail=newNode; } } public void display() { Node current=head; while(current!=null) { System.out.print(current.data+"<->"); current=current.next; } System.out.println("null"); } //删除节点 public void remove(int target) { Node current=head; while(current!=null) { if(current.data==target) { //更新相邻节点的指针 //如果当前结点为头结点，将头结点引用指向下一个 if(current.prev!=null) { current.prev.next=current.next; }else { head=current.next; } //如果当前结点为尾结点,将尾结点引用指向上一个 if(current.next!=null) { current.next.prev=current.prev; }else { tail=current.prev; } return; } current=current.next; } System.out.println("没找到该结点"); } }
链表的使用：添加结点以及删除结点
public class Test { public static void main(String[] args) { DoublyLinkedList linkedList=new DoublyLinkedList(); //添加四个结点 linkedList.append(1); linkedList.append(2); linkedList.append(3); linkedList.append(4); linkedList.display();//1<->2<->3<->4<->null linkedList.remove(3); linkedList.display();//1<->2<->4<->null } }
适用场景：
- 双向遍历：由于双向链表具有前向和后向指针，可以方便地进行双向遍历，这在某些算法和数据结构操作中很有用。
- 插入和删除：插入和删除节点的操作在双向链表中通常比单链表更高效，因为它不需要在删除节点时回溯到前一个节点。
- LRU缓存：双向链表常用于实现LRU（Least Recently Used）缓存淘汰策略，其中最近使用的元素移动到链表的尾部，最不常用的元素位于链表的头部，当缓存满时，可以轻松删除链表头部的元素。
- 编辑器和浏览器历史：双向链表可以用于实现文本编辑器的撤销和重做功能，以及浏览器历史记录的前进和后退功能，因为用户可以在双向链表中导航到前一个和后一个状态。
总之，双向链表在需要双向遍历、频繁插入和删除节点或实现某些特定数据结构时非常有用。然而，由于它需要额外的指针来维护前向链接，可能会占用更多的内存空间。所以在选择数据结构时，需要根据具体需求权衡其优点和缺点。
