如何用Java编写一个双链表实现？

本文共计1178个文字，预计阅读时间需要5分钟。

一、双向链表是什么？双向链表也称为双链表，是链表的一种。它的每个数据节点中包含两个指针，分别指向直接后继和直接前驱。因此，从双向链表中的任意一个节点开始，都可以很方便地访问到它的前驱和后继节点。这使得双向链表在遍历和修改时具有更高的灵活性。

一、双向链表是什么？

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。LinkedList底层就是一个双向链表，我们来实现一个双向链表。

这里多一个尾指针，方便我们对尾插操作从O(n)降到O(1).每个结点多了前驱结点，方便我们对链表进行操作。

二、具体方法实现

定义结点

class ListNode { int value; ListNode next; ListNode prev; public ListNode(int value) { this.value = value; } }

下标访问异常

public class IndexWrongException extends RuntimeException{ public IndexWrongException() { } public IndexWrongException(String message) { super(message); }}

获取链表长度

class ListNode { int value; ListNode next; ListNode prev; public ListNode(int value) { this.value = value; } }

打印链表

class ListNode { int value; ListNode next; ListNode prev; public ListNode(int value) { this.value = value; } }

清空链表

public void clear(){ if(this.head == null) { return; } ListNode cur = this.head; while(cur != null) { ListNode curNext = cur.next; cur.prev = null; cur.next = null; cur = curNext; } head = null; tail = null; }

头插法

public void addFirst(int data){ ListNode node = new ListNode(data); if(head == null) { this.head = node; this.tail = node; return; } node.next = this.head; this.head.prev = node; this.head = node; }

尾插法

public void addLast(int data){ ListNode node = new ListNode(data); if(head == null) { this.head = node; this.tail = node; return; } tail.next = node; node.prev = tail; tail = node; }

指定位置插入

public void addIndex(int index,int data) throws IndexWrongException{ if(index < 0 || index > size()) { throw new IndexWrongException("输入下标不合法"); } ListNode node = new ListNode(data); if(index == 0) { addFirst(data); return; } if(index == size()) { addLast(data); return; } ListNode cur = this.head; while(index != 0) { cur = cur.next; index--; } node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; }

查找元素

public boolean contains(int key){ if(head == null) { return false; } ListNode cur = this.head; while(cur != null) { if(cur.value == key) { return true; } cur = cur.next; } return false; }

删除第一次出现的关键字

public void remove(int key){ ListNode cur = head; while(cur != head) { if(cur.value == key) { if(cur == head) { head = head.next; if(head.next != null) { head.prev = null; }else { tail = null; } }else { cur.prev.next = cur.next; if(cur.next != null) { cur.next.prev = cur.prev; }else { tail = cur.prev; tail.next = null; } } return; } cur = cur.next; } }

删除所有值为key的节点

public void removeAllKey(int key){ ListNode cur = head; while(cur != head) { if(cur.value == key) { if(cur == head) { head = head.next; if(head.next != null) { head.prev = null; }else { tail = null; } }else { cur.prev.next = cur.next; if(cur.next != null) { cur.next.prev = cur.prev; }else { tail = cur.prev; tail.next = null; } } } cur = cur.next; } }

三、完整代码

public class LinkedList { static class ListNode { int value; ListNode next; ListNode prev; public ListNode(int value) { this.value = value; } } ListNode head; ListNode tail; //头插法 public void addFirst(int data){ ListNode node = new ListNode(data); if(head == null) { this.head = node; this.tail = node; return; } node.next = this.head; this.head.prev = node; this.head = node; } //尾插法 public void addLast(int data){ ListNode node = new ListNode(data); if(head == null) { this.head = node; this.tail = node; return; } tail.next = node; node.prev = tail; tail = node; } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data) throws IndexWrongException{ if(index < 0 || index > size()) { throw new IndexWrongException("输入下标不合法"); } ListNode node = new ListNode(data); if(index == 0) { addFirst(data); return; } if(index == size()) { addLast(data); return; } ListNode cur = this.head; while(index != 0) { cur = cur.next; index--; } node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ if(head == null) { return false; } ListNode cur = this.head; while(cur != null) { if(cur.value == key) { return true; } cur = cur.next; } return false; } //删除第一次出现关键字为key的节点 public void remove(int key){ ListNode cur = head; while(cur != head) { if(cur.value == key) { if(cur == head) { head = head.next; if(head.next != null) { head.prev = null; }else { tail = null; } }else { cur.prev.next = cur.next; if(cur.next != null) { cur.next.prev = cur.prev; }else { tail = cur.prev; tail.next = null; } } return; } cur = cur.next; } } //删除所有值为key的节点 public void removeAllKey(int key){ ListNode cur = head; while(cur != head) { if(cur.value == key) { if(cur == head) { head = head.next; if(head.next != null) { head.prev = null; }else { tail = null; } }else { cur.prev.next = cur.next; if(cur.next != null) { cur.next.prev = cur.prev; }else { tail = cur.prev; tail.next = null; } } } cur = cur.next; } } //得到单链表的长度 public int size(){ ListNode cur = head; int count = 0; while(cur != null) { cur = cur.next; count++; } return count; } public void display(){ ListNode cur = head; while (cur != null) { System.out.print(cur.value+" "); cur = cur.next; } System.out.println(); } public void clear(){ if(this.head == null) { return; } ListNode cur = this.head; while(cur != null) { ListNode curNext = cur.next; cur.prev = null; cur.next = null; cur = curNext; } head = null; tail = null; }}