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 指向链表尾节点，最后更新尾节点为新插入节点，插入过程如下图所示：
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;
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);
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实现双向链表(两个版本)
临近春节,项目都结束了,都等着回家过年了.下面是小编给大家研究数据结构的相关知识,链表算是经常用到的一种数据结构了,现将自己的实现展示如下,欢迎大神赐教. 第一个版本,没有最后一个节点,每次从根节点开始遍历 public class LinkedList<E> { private Node head; public LinkedList() { } public E getFirst(){ if(head==null){ return null; } return head.value; }
-
JAVA实现双向链表的增删功能的方法
JAVA实现双向链表的增删功能,完整代码 package linked; class LinkedTable{ } public class LinkedTableTest { //构造单链表 static Node node1 = new Node("name1"); static Node node2 = new Node("name2"); static Node node3 = new Node("name3"); static Node
-
Java双向链表按照顺序添加节点的方法实例
分析过程: 首先需要比较待添加的节点编号与已有的节点编号的大小,若待添加的节点编号已经存在,则不能加入.为防止出现空指针的情况,需要对节点的位置进行判断. 示例代码: package linkedlist; public class DoubleLinkedListDemo { public static void main(String[] args) { // 测试 System.out.println("双向链表的测试"); // 创建节点 Node node1 = new No
-
Java语言中链表和双向链表
链表是一种重要的数据结构,在程序设计中占有很重要的地位.C语言和C++语言中是用指针来实现链表结构的,由于Java语言不提供指针,所以有人认为在Java语言中不能实现链表,其实不然,Java语言比C和C++更容易实现链表结构.Java语言中的对象引用实际上是一个指针(本文中的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以编写这样的类来实现链表中的结点. class Node { Object data; Node next;//指向下一个结点 } 将数据域定义成Object类是因为
-
java数据结构之实现双向链表的示例
复制代码 代码如下: /** * 双向链表的实现 * @author Skip * @version 1.0 */public class DoubleNodeList<T> { //节点类 private static class Node<T>{ Node<T> perv; //前节点 Node<T> next; //后节点 T data; //数据 public Node(T t){ this.data = t; } } priv
-
java 实现双向链表实例详解
java 实现双向链表实例详解 双向链表是一个基本的数据结构,在Java中LinkedList已经实现了这种结构,不过作为开发者,也要拥有自己显示这种结构的能力.话不多说,上代码: 首先是链表的节点类: /** * 链表节点 * @author Administrator * * @param <T> */ public class ChainNode<T> { private T data; //对象编号 private int dataNo; public ChainN
-
java中使用双向链表实现贪吃蛇程序源码分享
使用双向链表实现贪吃蛇程序 1.链表节点定义: package snake; public class SnakeNode { private int x; private int y; private SnakeNode next; private SnakeNode ahead; public SnakeNode() { } public SnakeNode(int x, int y) { super(); this.x = x; this.y = y; } public int getX(
-
java数据结构基础:单链表与双向链表
目录 单链表: 实现思路: 代码实现: 双向链表: 实现思路: 代码实现: 总结 单链表: 每个数据是以节点的形式存在的 每个节点分为数据域和指针域 数据域中保存该节点的数据 指针域中保存指向下一个节点的指针 实现思路: 节点类SingleNode中保存数据和指向下一个节点的指针 单链表类SingleLinkedList中保存链表的头节点,实现相关链表方法 对于链表方法,涉及到位置查找,如在指定位置增加.删除节点,需要使用一个临时变量temp从头节点开始遍历,直至找到对应的位置. 对于节点的增加
-
Java中双向链表详解及实例
Java中双向链表详解及实例 写在前面: 双向链表是一种对称结构,它克服了单链表上指针单向性的缺点,其中每一个节点即可向前引用,也可向后引用,这样可以更方便的插入.删除数据元素. 由于双向链表需要同时维护两个方向的指针,因此添加节点.删除节点时指针维护成本更大:但双向链表具有两个方向的指针,因此可以向两个方向搜索节点,因此双向链表在搜索节点.删除指定索引处节点时具有较好的性能. Java语言实现双向链表: package com.ietree.basic.datastructure.dublin
-
java实现单链表、双向链表
本文实例为大家分享了java实现单链表.双向链表的相关代码,供大家参考,具体内容如下 java实现单链表: package code; class Node { Node next; int data; public Node(int data) { this.data=data; } } class LinkList { Node first; //头部 public LinkList() { this.first=null; } public void addNode(Node no) {