Java实现无头双向链表操作

Java实现无头双向链表操作

本文实例为大家分享了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. 头插法

/**

* 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 指向链表尾节http://点，最后更新尾节点为新插入节点，插入过程如下图所示：

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

*/

@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;

http:// node.prev = cur.prev;

cur.prev = node;

return true;

}

4. 查找是否包含关键字 key 在单链表中

/**

* 4.查找是否包含关键字 key 在单链表中

* @param key 要查找的关键字

* @return true/false

*/

@Override

public boolean contains(int key) {

Node cur = this.head;

while (cur != null) {

if (cur.data == key) {

return true;

}

cur = cur.next;

}

return false;

}

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

/**

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

* @param key

* @return

*/

@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;

}

6. 删除所有值为 key 的节点

/**

* 6.删除所有值为 key 的节点

* @param key

*/

@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;

}

}

7. 得到单链表的长度

/**

* 7.得到单链表的长度

* @return

*/

@Override

public int getLength() {

int count = 0;

Node cur = this.head;

while (cur != null) {

count++;

cur = cur.next;

}

return count;

}

8. 打印链表

/**

* 8.打印链表

*/

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

}

9. 清空顺序表以防内存泄漏

/**

* 9.清空顺序表以防内存泄漏

*/

@Override

public 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;

}

/**

* 1.头插法

* @param data

*/

@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;

}

}

/**

* 2.尾插法

* @param data

*/

@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("下标不合法！");

}

}

/**

* 3.任意位置插入，第一个数据节点为0号下标

* @param index 插入位置

* @param data 插入的值

* @return true/false

*/

@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 在单链表中

* @param key 要查找的关键字

* @return true/false

*/

@Override

public 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

*/

@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;

}

/**

* 6.删除所有值为 key 的节点

* @param key

*/

@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;

}

}

/**

* 7.得到单链表的长度

* @return

*/

@Override

public int getLength() {

int count = 0;

Node cur = this.head;

while (cur != null) {

count++;

cur = cur.next;

}

return count;

}

/**

* 8.打印链表

*/

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

}

/**

* 9.清空顺序表以防内存泄漏

*/

@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);

doublekgqJbkgSYLinked.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();

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。