这篇文章主要介绍了Java如何实现无头双向链表操作，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。
具体内容如下
无头双向链表的结构：
代码分析
节点结构
class Node { private int data; private Node next; private Node prev; public Node(int data) { this.data = data; this.prev = null; this.next = null; }} private Node head; // 头节点 private Node last; // 尾节点 public DoubleLinked() { this.head = null; this.last = null;}1. 头插法
public void addFirst(int data) { Node node = new Node(data); if (this.head == null) { this.head = node; this.last = node; } else { node.next = this.head; this.head.prev = node; this.head = node; }}先判断链表是否为空，若为空，则直接插入，头节点和尾节点都直接指向新插入的元素；
若链表不为空，则把要插入节点的 next 指向链表头节点，头节点的 prev 指向新插入的节点，最后更新头节点为新插入节点，插入过程如下图所示：
2. 尾插法
public void addLast(int data) { Node node = new Node(data); if (this.head == null) { this.head = node; this.last = node; } else { this.last.next = node; node.prev = this.last; this.last = node; }}若链表为空，同头插法；
若链表不为空，则把链表尾节点的 next 指向要插入节点，要插入节点的 prev 指向链表尾节点，最后更新尾节点为新插入节点，插入过程如下图所示：
3. 查找是否包含关键字 key 在单链表中
// 查找 private Node searchIndex(int index) { checkIndex(index); int count = 0; Node cur = this.head; while (count != index) { cur = cur.next; count++; } return cur; } // 合法性检查 private void checkIndex(int index) { if (index < 0 || index > getLength()) { throw new IndexOutOfBoundsException("下标不合法！"); } } @Override public boolean addIndex(int index, int data) { if (index ==0) { addFirst(data); return true; } if (index == getLength()) { addLast(data); return true; } // cur 指向index位置的节点 Node cur = searchIndex(index); Node node = new Node(data); node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; return true; }
4. 查找是否包含关键字 key 在单链表中
@Overridepublic boolean contains(int key) { Node cur = this.head; while (cur != null) { if (cur.data == key) { return true; } cur = cur.next; } return false;}5. 删除第一次出现关键字为 key 的节点
@Overridepublic int remove(int key) { Node cur = this.head; int oldData = 0; while (cur != null) { if (cur.data == key) { oldData = cur.data; // 头节点 if (cur == this.head) { this.head = this.head.next; this.head.prev = null; } else { // cur.next != null --->不是尾节点 if (cur.next != null) { cur.next.prev = cur.prev; } else { this.last = cur.prev; } } return oldData; } cur = cur.next; } return -1;}
6. 删除所有值为 key 的节点
@Overridepublic void removeAllKey(int key) { Node cur = this.head; while (cur != null) { if (cur.data == key) { // 头节点 if (cur == this.head) { this.head = this.head.next; this.head.prev = null; } else { cur.prev.next = cur.next; // cur.next != null --->不是尾节点 if (cur.next != null) { cur.next.prev = cur.prev; } else { this.last = cur.prev; } } } cur = cur.next; }}7. 得到单链表的长度
@Overridepublic int getLength() { int count = 0; Node cur = this.head; while (cur != null) { count++; cur = cur.next; } return count;}8. 打印链表
@Overridepublic void display() { if (this.head == null) { return ; } Node cur = this.head; while (cur != null) { System.out.print(cur.data + " "); cur = cur.next; } System.out.println();}9. 清空顺序表以防内存泄漏
@Overridepublic void clear() { while(this.head != null) { Node cur = this.head.next; this.head.next = null; this.head.prev = null; this.head = cur; }}接口、实现方法、测试
1. 接口
package com.github.doubly;// 不带头节点单链表的实现public interface IDoubleLinked { // 1.头插法 void addFirst(int data); // 2.尾插法 void addLast(int data); // 3.任意位置插入，第一个数据节点为0号下标 boolean addIndex(int index, int data); // 4.查找是否包含关键字 key 在单链表中 boolean contains(int key); // 5.删除第一次出现关键字为 key 的节点 int remove(int key); // 6.删除所有值为 key 的节点 void removeAllKey(int key); // 7.得到单链表的长度 int getLength(); // 8.打印链表 void display(); // 9.清空顺序表以防内存泄漏 void clear();}2. 实现方法
package com.github.doubly;public class DoubleLinked implements IDoubleLinked { class Node { private int data; private Node next; private Node prev; public Node(int data) { this.data = data; this.prev = null; this.next = null; } } private Node head; // 头节点 private Node last; // 尾节点 public DoubleLinked() { this.head = null; this.last = null; } @Override public void addFirst(int data) { Node node = new Node(data); if (this.head == null) { this.head = node; this.last = node; } else { node.next = this.head; this.head.prev = node; this.head = node; } } @Override public void addLast(int data) { Node node = new Node(data); if (this.head == null) { this.head = node; this.last = node; } else { this.last.next = node; node.prev = this.last; this.last = node; } } // 查找 private Node searchIndex(int index) { checkIndex(index); int count = 0; Node cur = this.head; while (count != index) { cur = cur.next; count++; } return cur; } // 合法性检查 private void checkIndex(int index) { if (index < 0 || index > getLength()) { throw new IndexOutOfBoundsException("下标不合法！"); } } @Override public boolean addIndex(int index, int data) { if (index ==0) { addFirst(data); return true; } if (index == getLength()) { addLast(data); return true; } // cur 指向index位置的节点 Node cur = searchIndex(index); Node node = new Node(data); node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; return true; } @Override public boolean contains(int key) { Node cur = this.head; while (cur != null) { if (cur.data == key) { return true; } cur = cur.next; } return false; } @Override public int remove(int key) { Node cur = this.head; int oldData = 0; while (cur != null) { if (cur.data == key) { oldData = cur.data; // 头节点 if (cur == this.head) { this.head = this.head.next; this.head.prev = null; } else { // cur.next != null --->不是尾节点 if (cur.next != null) { cur.next.prev = cur.prev; } else { this.last = cur.prev; } } return oldData; } cur = cur.next; } return -1; } @Override public void removeAllKey(int key) { Node cur = this.head; while (cur != null) { if (cur.data == key) { // 头节点 if (cur == this.head) { this.head = this.head.next; this.head.prev = null; } else { cur.prev.next = cur.next; // cur.next != null --->不是尾节点 if (cur.next != null) { cur.next.prev = cur.prev; } else { this.last = cur.prev; } } } cur = cur.next; } } @Override public int getLength() { int count = 0; Node cur = this.head; while (cur != null) { count++; cur = cur.next; } return count; } @Override public void display() { if (this.head == null) { return ; } Node cur = this.head; while (cur != null) { System.out.print(cur.data + " "); cur = cur.next; } System.out.println(); } @Override public void clear() { while(this.head != null) { Node cur = this.head.next; this.head.next = null; this.head.prev = null; this.head = cur; } }}3. 测试
package com.github.doubly;public class TestDemo { public static void main(String[] args) { DoubleLinked doubleLinked = new DoubleLinked(); doubleLinked.addFirst(10); doubleLinked.addFirst(20); doubleLinked.addFirst(30); doubleLinked.addFirst(40); doubleLinked.addFirst(50); doubleLinked.display(); doubleLinked.addIndex(0,100); doubleLinked.addIndex(1,200); doubleLinked.addIndex(0,300); doubleLinked.addLast(40); doubleLinked.addLast(50); doubleLinked.display(); doubleLinked.remove(300); doubleLinked.display(); doubleLinked.removeAllKey(50); doubleLinked.display(); }}
感谢你能够认真阅读完这篇文章，希望小编分享的“Java如何实现无头双向链表操作”这篇文章对大家有帮助，同时也希望大家多多支持编程网，关注编程网行业资讯频道，更多相关知识等着你来学习!
