双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
双向链表
在实现双向链表的时候，
add和remove、node方法需要重新实现，链表结点需要进行添加一个前驱结点，需要添加一个指向链表尾节点的指针。其他方法可以参考单向链表 【数据结构与算法】03 - 单向循环链表
1. 修改Node实体
在实体中增加一个前驱结点；
/**
* 创建一个节点实体
*
* @param <E>
*/
static class Node<E> {
Node<E> prev;
E element;
Node<E> next;
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
/**
* 重写节点的 toString 方法
*
* @return
*/
@Override
public String toString() {
StringBuilder str = new StringBuilder();
if (prev != null) {
str.append(prev.element);
} else {
str.append("null");
}
str.append("_").append(element).append("_");
if (next != null) {
str.append(next.element);
} else {
str.append("null");
}
return str.toString();
}
}
2. 修改node方法实现
node方法用于获取指定 index位置的结点并返回，为了提高链表的查找效率，使用向前获取向后查找的方式。当需要查找的index位于总结点数的前半段的时候从前往后进行查找，当位于后半段的时候从后往前进行查找:
/**
* 获取指定 index 位置处的节点
*
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheckIndex(index);
// 因为是双向链表可以进行从前查找或者从后查找的原则
if (index < size >> 1) {
Node<E> node = first;
// 如果index是在链表的前半段则进行从前往后查找的方式
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
3. 对 add添加结点的方法进行实现
/**
* 向指定 index 位置插入节点
*
* @param index
* @param element
*/
@Override
public void add(int index, E element) {
rangeCheckIndexForAdd(index);
// 当在最后插入节点或者是 链表中没有节点得时候
if (index == size) {
// 只想原始得尾指针
Node<E> oldLast = last;
last = new Node<>(oldLast, element, null);
if (oldLast == null) {
first = last;
} else {
oldLast.next = last;
}
} else {
// 需要找到需要插入节点位置处得原始节点
// 这是即将插入节点得下一个节点
Node<E> next = node(index);
// 即将插入节点得上一个节点
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;
if (prev == null) {
// 表示是在第一个节点前插入得时候
first = node;
} else {
prev.next = node;
}
}
size++;
}
4. 对 remove进行修改
/**
* 删除指定 index 位置的节点
*
* @param index
* @return
*/
@Override
public E remove(int index) {
rangeCheckIndex(index);
// 获取需要删除的节点
Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
// 可能上一个节点时 null
if (prev == null) {
first = next;
} else {
prev.next = next;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
}
size--;
return node.element;
}
5. 对 clear 清空链表的方法进行修改
/**
* 清空链表
*/
@Override
public void clear() {
first = null;
last = null;
size = 0;
}
6. 全部实现代码
6.1 接口定义
public interface List<T> {
final static int ELEMENT_NOT_FOUND = -1;
int size();
boolean isEmpty();
boolean contains(T element);
void add(T element);
void add(int index, T element);
T get(int index);
T set(int index, T element);
T remove(int index);
int indexOf(T element);
void clear();
}
6.2 抽象类实现公共的方法
/**
* Description: dsai
* Created by itLu on 2021/6/26 10:45
*
* @author yanpeng.lu
*/
public abstract class AbstractLinkedList<T> implements List<T> {
/**
* 链表中元素的个数
*/
protected int size;
/**
* 获取当前链表中元素的个数
*
* @return
*/
@Override
public int size() {
return size;
}
/**
* 判断当前链表是否为空
*
* @return
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* 判断链表中是否存在某个元素
*
* @param element
* @return
*/
@Override
public boolean contains(T element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 向链表的末尾添加一个节点
*
* @param element
*/
@Override
public void add(T element) {
add(size, element);
}
/**
* 校验 index 是否合法
*
* @param index
*/
protected void rangeCheckIndex(int index) {
if (index < 0 || index >= size) {
outOfBound(index);
}
}
/**
* 统一处理 index 越界
*
* @param index
*/
private void outOfBound(int index) {
throw new IndexOutOfBoundsException("index : " + index + " size : " + size);
}
/**
* @param index
* 针对添加节点的index校验
*/
protected void rangeCheckIndexForAdd(int index) {
if (index < 0 || index > size) {
outOfBound(index);
}
}
}
6.3 实现自己独有的方法
/**
* Description: dsai
* Created by itLu on 2021/6/26 15:35
*
* @author yanpeng.lu
*/
public class DoublyLinkedList<E> extends AbstractLinkedList<E> {
/**
* 指向头节点的指针 上一个节点 prev 是 null
*/
private Node<E> first;
/**
* 指向尾节点的指针 下一个节点 next 是 null
*/
private Node<E> last;
/**
* 创建一个节点实体
*
* @param <E>
*/
static class Node<E> {
Node<E> prev;
E element;
Node<E> next;
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
/**
* 重写节点的 toString 方法
*
* @return
*/
@Override
public String toString() {
StringBuilder str = new StringBuilder();
if (prev != null) {
str.append(prev.element);
} else {
str.append("null");
}
str.append("_").append(element).append("_");
if (next != null) {
str.append(next.element);
} else {
str.append("null");
}
return str.toString();
}
}
/**
* 向指定 index 位置插入节点
*
* @param index
* @param element
*/
@Override
public void add(int index, E element) {
rangeCheckIndexForAdd(index);
// 当在最后插入节点或者是 链表中没有节点得时候
if (index == size) {
// 只想原始得尾指针
Node<E> oldLast = last;
last = new Node<>(oldLast, element, null);
if (oldLast == null) {
first = last;
} else {
oldLast.next = last;
}
} else {
// 需要找到需要插入节点位置处得原始节点
// 这是即将插入节点得下一个节点
Node<E> next = node(index);
// 即将插入节点得上一个节点
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;
if (prev == null) {
// 表示是在第一个节点前插入得时候
first = node;
} else {
prev.next = node;
}
}
size++;
}
/**
* 获取指定 index 位置得元素值
*
* @param index
* @return
*/
@Override
public E get(int index) {
return node(index).element;
}
/**
* 覆盖指定 index 位置得元素值
*
* @param index
* @param element
* @return
*/
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E oldElement = node.element;
node.element = element;
return oldElement;
}
/**
* 删除指定 index 位置的节点
*
* @param index
* @return
*/
@Override
public E remove(int index) {
rangeCheckIndex(index);
// 获取需要删除的节点
Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
// 可能上一个节点时 null
if (prev == null) {
first = next;
} else {
prev.next = next;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
}
size--;
return node.element;
}
/**
* 获取指定元素在链表中的位置
*
* @param element
* @return
*/
@Override
public int indexOf(E element) {
Node<E> node = first;
if (element == null) {
for (int i = 0; i < size; i++) {
if (node.element == null) {
return i;
}
node = node.next;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) {
return i;
}
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 清空链表
*/
@Override
public void clear() {
first = null;
last = null;
size = 0;
}
/**
* 获取指定 index 位置处的节点
*
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheckIndex(index);
// 因为是双向链表可以进行从前查找或者从后查找的原则
if (index < size >> 1) {
Node<E> node = first;
// 如果index是在链表的前半段则进行从前往后查找的方式
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
/**
* 重写toString方法
*
* @return
*/
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append("size : ").append(size).append(" [ ");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
str.append(" , ");
}
str.append(node);
node = node.next;
}
str.append(" ] ");
return str.toString();
}
}
