引言
前面几篇文章详细学习了单链表的操作，有了这个基础，双链表的实现便水到渠成。由于它的基本实现和单链表基本一样，所以本篇仅仅简单说明一下它的实现，细节原理不再详述。
双链表实现
1.接口和实现:和单链表的实现接口一致
public interface IList<T> {
int size();
boolean isEmpty();
void clear();
boolean contains(T item);
boolean add(T item);
T get(int index);
T set(int index, T item);
void add(int index, T item);
T remove(int index);
}
为了统一删除和增加的操作位置，引入不带数据的头结点和指向尾元素的尾指针，这样增加和删除操作只分两种情况:尾部操作和中间操作.
/**
* Created by chenming on 2018/5/26
*/
public class DLinkedList<T> implements IList<T> {
private DNode<T> head; //不带数据的头结点
private DNode<T> tail; //指向尾部的指针
public DLinkedList() {
//初始化头结点
this.head = this.tail = new DNode<>();
}
......
}
2.节点:和单链表相比多了个前驱指针。
package List.dlinkedlist;
/**
* Created by chenming on 2018/5/26
*/
public class DNode<T> {
public T data;
public DNode<T> prev, next;//前继指针和后继指针
public DNode(T data, DNode<T> prev, DNode<T> next) {
this.data = data;
this.prev = prev;
this.next = next;
}
public DNode(T data) {
this(data, null, null);
}
public DNode() {
this(null, null, null);
}
}
3.添加元素,和单链表类似，分为尾部添加和中间添加。
/**
* 指定位置添加元素
*
* @param index
* @param item
*/
@Override
public void add(int index, T item) {
if (index < 0) {
throw new IndexOutOfBoundsException();
}
if (item == null) {
return;
}
DNode<T> preNode = this.head;
int j = 0;
//查找要插入结点位置的前一个结点
while (preNode.next != null && j < index) {
j++;
preNode = preNode.next;
}
//创建需要插入的结点,并让其前继指针指向front,后继指针指向front.next
DNode<T> newNode = new DNode<>(item, preNode, preNode.next);
//表中间插入preNode的下一个节点的前驱节点指向新节点
if (preNode.next != null) {
preNode.next.prev = newNode;
}
//preNode的后继指针指向新节点
preNode.next = newNode;
if (preNode == tail) {//尾部添加元素，更新尾部指针
tail = newNode;
}
}
/**
* 尾部添加元素
*
* @param item
* @return
*/
@Override
public boolean add(T item) {
if (item == null) {
return false;
}
//创建需要插入的结点,并让其前继指针指向tail,后继指针指向tail.next
DNode<T> newNode = new DNode<>(item, tail, tail.next);
//tail的后继指针指向新节点
tail.next = newNode;
//修改tail
tail = newNode;
return true;
}
4.删除元素：分为尾部删除和中间删除。
/**
* 删除元素
*
* @param index
* @return
*/
@Override
public T remove(int index) {
int size = size();
if (index < 0 || index >= size || isEmpty()) {
return null;
}
DNode<T> p = this.head.next;
int j = 0;
//找到要删除的位置,index = 0指向head.next，所以条件为j <= index
while (p != null && j < index) {
p = p.next;
j++;
}
if (j >= size()) {//数组越界
throw new IndexOutOfBoundsException();
}
//链表中间删除元素
if (p.next != null) {
p.next.prev = p.prev;
}
p.prev.next = p.next;
//如果是尾节点则更改tail为p的前驱节点
if (p == tail) {
tail = p.prev;
}
return p.data;
}
/**
* 删除所有item元素
* @param item
* @return
*/
public boolean removeAll(T item) {
boolean result = false;
if (item == null || isEmpty()) {
return result;
}
DNode<T> p = this.head.next;
while (p != null) {
if (item.equals(p.data)) {//删除操作
if (p == tail) {//p为尾部节点.更新尾节点指向,删除p
tail = p.prev;
tail.next = null;
p.prev = null;
} else {//删除中间节点
p.prev.next = p.next;
p.next.prev = p.prev;
}
result = true;
}
p = p.next;//继续查找
}
return result;
}
5.读取和设置元素。
@Override
public T get(int index) {
if (index < 0) {
throw new IndexOutOfBoundsException();
}
int j = 0;
DNode<T> node = this.head.next;
while (node != null && j < index) {
node = node.next;
j++;
}
if (j >= size()) {//数组越界
throw new IndexOutOfBoundsException();
}
if (node != null) {
return node.data;
}
return null;
}
/**
* 设置元素
*
* @param index
* @param item
* @return
*/
@Override
public T set(int index, T item) {
if (index < 0) {
throw new IndexOutOfBoundsException();
}
if (index >= size()) {//数组越界
throw new IndexOutOfBoundsException();
}
T old = null;
int j = 0;
DNode<T> node = this.head.next;
while (node != null && j < index) {
node = node.next;
j++;
}
if (node != null) {
old = node.data;
node.data = item;
return old;
}
return null;
}
6.其他方法:
/**
* 链表大小
*
* @return
*/
@Override
public int size() {
int size = 0;
DNode<T> node = head.next;//从head.next开始
while (node != null) {
node = node.next;
size++;
}
return size;
}
@Override
public boolean isEmpty() {
return head == tail;
}
@Override
public void clear() {
head = tail = new DNode<>();
}
@Override
public boolean contains(T item) {
if (item == null) {
return false;
}
DNode<T> p = head.next;
while (p != null) {
if (item.equals(p.data)) {
return true;
}
p = p.next;
}
return false;
}
JDK里的LinkedList就是基于双链表实现，它在此基础上进行了优化，具体实现方法会在后面的LinkedList源码分析进行说明。完整代码地址:数据结构与算法学习JAVA描述GayHub地址
