双端链表
链表中保存着对最后一个链结点引用的链表。
可以方便的从尾结点插入数据。
代码
public class Node {
// 数据域
public long data;
//指针域（保存下一个节点的引用）
public Node next;
public Node(long value) {
this.data = value;
}
/**
* 显示方法
*/
public void display() {
System.out.print(data + " ");
}
}
/**
* 双端链表
*/
public class DoubleEndLinkedList {
// 头结点
private Node first;
//尾结点
private Node last;
public DoubleEndLinkedList() {
first = null;
last = null;
}
/**
* 插入一个节点，在头结点后进行插入
*
* @param value
*/
public void insertFirst(long value) {
Node node = new Node(value);
if (isEmpty()) {
last = node;
}
node.next = first;
first = node;
}
public void insertLast(long value) {
Node node = new Node(value);
if (isEmpty()) {
first = node;
} else {
last.next = node;
}
last = node;
}
/**
* 删除一个结点
*
* @return
*/
public Node deleteFirst() {
Node tmp = first;
if (first.next == null) {
last = null;
}
first = tmp.next;
return tmp;
}
/**
* 显示方法
*/
public void display() {
Node current = first;
while (current != null) {
current.display();
current = current.next;
}
}
/**
* 查找方法
*
* @param value
* @return
*/
public Node find(long value) {
Node current = first;
while (current.data != value) {
if (current.next == null) {
return null;
}
current = current.next;
}
return current;
}
public Node delete(long value) {
Node current = first;
Node previous = first;
while (current.data != value) {
if (current.next == null) {
return null;
}
previous = current;
current = current.next;
}
if (current == first) {
first = first.next;
} else {
previous.next = current.next;
}
return current;
}
/**
* 判断是否为空
*
* @return
*/
public boolean isEmpty() {
return first == null;
}
}
测试
public class TestDoubleEndLinkedList {
public static void main(String[] args) {
DoubleEndLinkedList listFirst = new DoubleEndLinkedList();
listFirst.insertFirst(0);
listFirst.insertFirst(1);
listFirst.insertFirst(2);
listFirst.display();
System.out.println();
listFirst.deleteFirst();
listFirst.deleteFirst();
listFirst.display();
System.out.println();
System.out.println("-----");
DoubleEndLinkedList listLast = new DoubleEndLinkedList();
listLast.insertLast(3);
listLast.insertLast(4);
listLast.insertLast(5);
listLast.display();
System.out.println();
listLast.deleteFirst();
listLast.display();
}
}
结果
···
2 1 0
0
3 4 5
4 5
···
双向链表
双端链表可以方便的从尾结点插入数据，但是不能从尾部删除数据，所以引入双向链表。
双向链表每个结点除了保存对下一个结点的引用，同时还保存者前一个结点的引用。
代码
public class Node {
// 数据域
public long data;
//指针域（保存下一个节点的引用）
public Node next;
//指针域（保存前一个节点的引用）
public Node previous;
public Node(long value) {
this.data = value;
}
/**
* 显示方法
*/
public void display() {
System.out.print(data + " ");
}
}
/**
* 双向链表
*/
public class DoubleByLinkedList {
// 头结点
private Node first;
//尾结点
private Node last;
public DoubleByLinkedList() {
first = null;
last = null;
}
/**
* 插入一个节点，在头结点后进行插入
*
* @param value
*/
public void insertFirst(long value) {
Node node = new Node(value);
if (isEmpty()) {
last = node;
} else {
first.previous = node;
}
node.next = first;
first = node;
}
public void insertLast(long value) {
Node node = new Node(value);
if (isEmpty()) {
first = node;
} else {
last.next = node;
node.previous = last;
}
last = node;
}
/**
* 删除一个结点,在头结点后进行删除
*
* @return
*/
public Node deleteFirst() {
Node tmp = first;
if (first.next == null) {
last = null;
} else {
first.next.previous = null;
}
first = tmp.next;
return tmp;
}
/**
* 删除一个结点,从尾部进行删除
*
* @return
*/
public Node deleteLast() {
if (first.next == null) {
first = null;
} else {
last.previous.next = null;
}
last = last.previous;
return last;
}
/**
* 显示方法
*/
public void display() {
Node current = first;
while (current != null) {
current.display();
current = current.next;
}
}
/**
* 查找方法
*
* @param value
* @return
*/
public Node find(long value) {
Node current = first;
while (current.data != value) {
if (current.next == null) {
return null;
}
current = current.next;
}
return current;
}
public Node delete(long value) {
Node current = first;
while (current.data != value) {
if (current.next == null) {
return null;
}
current = current.next;
}
if (current == first) {
first = first.next;
} else {
current.previous.next = current.next;
}
return current;
}
/**
* 判断是否为空
*
* @return
*/
public boolean isEmpty() {
return first == null;
}
}
测试
public class TestDoubleByLinkedList {
public static void main(String[] args) {
DoubleByLinkedList dl = new DoubleByLinkedList();
dl.insertLast(0);
dl.insertLast(1);
dl.insertLast(2);
dl.display();
System.out.println();
while (!dl.isEmpty()){
dl.deleteLast();
System.out.println();
dl.display();
}
}
}
结果
0 1 2
0 1
0
网友评论