Java实现无头双向链表操作 Java实现无头双向链表操作

本文实例为大家分享了Java实现无头双向链表的具体代码，供大家参考，具体内容如下
无头双向链表的结构：
文章图片

代码分析节点结构

class Node {private int data; private Node next; private Node prev; public Node(int data) {this.data = https://www.it610.com/article/data; this.prev = null; this.next = null; }}private Node head; // 头节点private Node last; // 尾节点public DoubleLinked() {this.head = null; this.last = null; }

1. 头插法

/*** 1.头插法* @param data*/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. 尾插法

/*** 2.尾插法* @param data*/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("下标不合法！"); }}/*** 3.任意位置插入，第一个数据节点为0号下标* @param index 插入位置* @param data 插入的值* @return true/false*/@Overridepublic 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 在单链表中

/** * 4.查找是否包含关键字 key 在单链表中 * @param key 要查找的关键字 * @return true/false */@Overridepublic boolean contains(int key) {Node cur = this.head; while (cur != null) {if (cur.data =https://www.it610.com/article/= key) {return true; }cur = cur.next; }return false; }

5. 删除第一次出现关键字为 key 的节点

/** * 5.删除第一次出现关键字为 key 的节点 * @param key * @return */@Overridepublic int remove(int key) {Node cur = this.head; int oldData = https://www.it610.com/article/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 的节点

/** * 6.删除所有值为 key 的节点 * @param key */@Overridepublic void removeAllKey(int key) {Node cur = this.head; while (cur != null) {if (cur.data =https://www.it610.com/article/= 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. 得到单链表的长度

/** * 7.得到单链表的长度 * @return */@Overridepublic int getLength() {int count = 0; Node cur = this.head; while (cur != null) {count++; cur = cur.next; }return count; }

8. 打印链表

/** * 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. 清空顺序表以防内存泄漏

/** * 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 = https://www.it610.com/article/data; this.prev = null; this.next = null; }}private Node head; // 头节点private Node last; // 尾节点public DoubleLinked() {this.head = null; this.last = null; }/*** 1.头插法* @param data*/@Overridepublic 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; }}/*** 2.尾插法* @param data*/@Overridepublic 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("下标不合法！"); }}/*** 3.任意位置插入，第一个数据节点为0号下标* @param index 插入位置* @param data 插入的值* @return true/false*/@Overridepublic 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 在单链表中* @param key 要查找的关键字* @return true/false*/@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 的节点* @param key* @return*/@Overridepublic int remove(int key) {Node cur = this.head; int oldData = https://www.it610.com/article/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 的节点* @param key*/@Overridepublic void removeAllKey(int key) {Node cur = this.head; while (cur != null) {if (cur.data =https://www.it610.com/article/= 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.得到单链表的长度* @return*/@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; }}}

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(); }}