Java无头双向链表操作
Sasura_321 人气:0无头双向链表的结构：
代码分析
节点结构
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();
}
}
加载全部内容