05、数据结构和算法 - 实战：Java实现双向链表
1.1 什么是双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
1、 value域–存放结点值的数据域；
2、 prev域–存放结点的直接前继的地址（位置）的指针域（链域）；
3、 next域–存放结点的直接后继的地址（位置）的指针域（链域）；
双向链表是通过上述定义的结点使用 prev 以及 next 域依次串联在一起而形成的。
1.2 JAVA实现双向链表
CustomDoublyLinkedList类是一个自定义实现了双向链表。
package com.yuanxw.datastructure.chapter5;
/**
* 自定义双向链表
* @param <E>
*/
public class CustomDoublyLinkedList<E> {
/**
* Node数据结构
* Node内部类，外部无法访问
*
* @param <E>
*/
private static class Node<E> {
// Node节点value值
private E value;
// 上一个Node节点
private Node<E> prev;
// 下一个Node节点
private Node<E> next;
}
// 头节点元素
private Node<E> first;
// 尾节点元素
private Node<E> last;
// 自定义LinkedList大小
private int size;
/**
* 添加头节点元素
*
* @param element
* @return
*/
public boolean addFirst(E element) {
Node newNode = new Node();
newNode.value = element;
newNode.next = first;
if (isEmpty()) {
last = newNode;
first = newNode;
} else {
first.prev = newNode;
newNode.next = first;
}
first = newNode;
size++;
return true;
}
/**
* 向尾节点添加元素
* @param element
* @return
*/
public boolean addLast(E element) {
Node newNode = new Node();
newNode.value = element;
if (isEmpty()) {
last = newNode;
first = newNode;
} else {
newNode.prev = last;
last.next = newNode;
}
last = newNode;
size++;
return true;
}
/**
* 获得最后一个元素
* @return
*/
public E getLast(){
return last.value;
}
/**
* 获得第一个元素
* @return
*/
public E getFirst(){
return first.value;
}
/**
* 判断是否为空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含指定元素
* @param element
* @return
*/
private boolean contains(E element) {
Node<E> currentNode = this.first;
while (currentNode != null){
if(currentNode.value.equals(element)){
return true;
}
currentNode = currentNode.next;
}
return false;
}
/**
* 获得指定元素的下一个元素
* @param element
* @return
*/
private E getNext(E element){
Node<E> currentNode = this.first;
while (currentNode != null){
if(currentNode.value.equals(element) && currentNode.next != null){
return currentNode.next.value;
}
currentNode = currentNode.next;
}
return null;
}
/**
* 获得指定元素的上一个元素
* @param element
* @return
*/
private E getPrev(E element){
Node<E> currentNode = this.first;
while (currentNode != null){
if(currentNode.value.equals(element)){
return currentNode.prev.value;
}
currentNode = currentNode.next;
}
return null;
}
/**
* 删除指定元素
* @param element
* @return
*/
public boolean remove(E element){
Node<E> currentNode = this.first;
boolean flag = false;
while (currentNode != null){
if(currentNode.value.equals(element)){
currentNode.prev.next = currentNode.next;
currentNode.next.prev = currentNode.prev;
flag = true;
}
currentNode = currentNode.next;
}
return flag;
}
/**
* 重写toString方法，方便显示
*
* @return
*/
@Override
public String toString() {
StringBuffer buffer = new StringBuffer();
if (this.isEmpty()) {
buffer.append("[]");
return buffer.toString();
}
buffer.append("[");
Node<E> currentNode = this.first;
while (currentNode != null) {
buffer.append(currentNode.value).append(",");
currentNode = currentNode.next;
}
buffer.deleteCharAt(buffer.length() - 1);
buffer.append("]");
return buffer.toString();
}
public static void main(String[] args) {
CustomDoublyLinkedList customDoublyLinkedList = new CustomDoublyLinkedList();
System.out.println("addLast()添加链表头节点元素【西直门】: " + customDoublyLinkedList.addLast("西直门"));
System.out.println("addLast()添加链表头节点元素【鼓楼大街】: " + customDoublyLinkedList.addLast("鼓楼大街"));
System.out.println("addLast()添加链表头节点元素【安定门】: " + customDoublyLinkedList.addLast("安定门"));
System.out.println("addLast()添加链表头节点元素【东直门】: " + customDoublyLinkedList.addLast("东直门"));
System.out.println("addLast()添加链表头节点元素【东四十条】: " + customDoublyLinkedList.addLast("东四十条"));
System.out.println("------------------------------------------------------------------------------------");
System.out.println("addFirst()添加链表头节点元素【车公庄】: " + customDoublyLinkedList.addFirst("车公庄"));
System.out.println("addFirst()添加链表头节点元素【阜成门】: " + customDoublyLinkedList.addFirst("阜成门"));
System.out.println("addFirst()添加链表头节点元素【复兴门】: " + customDoublyLinkedList.addFirst("复兴门"));
System.out.println("------------------------------------------------------------------------------------");
System.out.println("getFirst()获得第一个元素: " + customDoublyLinkedList.getFirst());
System.out.println("getLast()获得第最后一个元素: " + customDoublyLinkedList.getLast());
System.out.println("------------------------------------------------------------------------------------");
System.out.println("查看列出customDoublyLinkedList对象所有节点元素：" + customDoublyLinkedList);
System.out.println("getPrev()指定【阜成门】元素上一个元素: " + customDoublyLinkedList.getPrev("阜成门"));
System.out.println("getNext()指定【阜成门】元素下一个元素: " + customDoublyLinkedList.getNext("阜成门"));
System.out.println("------------------------------------------------------------------------------------");
System.out.println("remove()删除指定元素【东四十条】: " + customDoublyLinkedList.remove("安定门"));
System.out.println("查看列出customDoublyLinkedList对象所有节点元素：" + customDoublyLinkedList);
System.out.println("------------------------------------------------------------------------------------");
}
}
执行结果：
addLast()添加链表头节点元素【西直门】: true
addLast()添加链表头节点元素【鼓楼大街】: true
addLast()添加链表头节点元素【安定门】: true
addLast()添加链表头节点元素【东直门】: true
addLast()添加链表头节点元素【东四十条】: true
------------------------------------------------------------------------------------
addFirst()添加链表头节点元素【车公庄】: true
addFirst()添加链表头节点元素【阜成门】: true
addFirst()添加链表头节点元素【复兴门】: true
------------------------------------------------------------------------------------
getFirst()获得第一个元素: 复兴门
getLast()获得第最后一个元素: 东四十条
------------------------------------------------------------------------------------
查看列出customDoublyLinkedList对象所有节点元素：[复兴门,阜成门,车公庄,西直门,鼓楼大街,安定门,东直门,东四十条]
getPrev()指定【阜成门】元素上一个元素: 复兴门
getNext()指定【阜成门】元素下一个元素: 车公庄
------------------------------------------------------------------------------------
remove()删除指定元素【东四十条】: true
查看列出customDoublyLinkedList对象所有节点元素：[复兴门,阜成门,车公庄,西直门,鼓楼大街,东直门,东四十条]
------------------------------------------------------------------------------------