引言
前面幾篇文章詳細(xì)學(xué)習(xí)了單鏈表的操作，有了這個基礎(chǔ)渡嚣，雙鏈表的實(shí)現(xiàn)便水到渠成。由于它的基本實(shí)現(xiàn)和單鏈表基本一樣肥印，所以本篇僅僅簡單說明一下它的實(shí)現(xiàn)，細(xì)節(jié)原理不再詳述。
雙鏈表實(shí)現(xiàn)
1.接口和實(shí)現(xiàn):和單鏈表的實(shí)現(xiàn)接口一致
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);
}
為了統(tǒng)一刪除和增加的操作位置招驴，引入不帶數(shù)據(jù)的頭結(jié)點(diǎn)和指向尾元素的尾指針棺蛛，這樣增加和刪除操作只分兩種情況:尾部操作和中間操作.
/**
* Created by chenming on 2018/5/26
*/
public class DLinkedList<T> implements IList<T> {
private DNode<T> head; //不帶數(shù)據(jù)的頭結(jié)點(diǎn)
private DNode<T> tail; //指向尾部的指針
public DLinkedList() {
//初始化頭結(jié)點(diǎn)
this.head = this.tail = new DNode<>();
}
......
}
2.節(jié)點(diǎn):和單鏈表相比多了個前驅(qū)指針。
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;
//查找要插入結(jié)點(diǎn)位置的前一個結(jié)點(diǎn)
while (preNode.next != null && j < index) {
j++;
preNode = preNode.next;
}
//創(chuàng)建需要插入的結(jié)點(diǎn),并讓其前繼指針指向front,后繼指針指向front.next
DNode<T> newNode = new DNode<>(item, preNode, preNode.next);
//表中間插入preNode的下一個節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)指向新節(jié)點(diǎn)
if (preNode.next != null) {
preNode.next.prev = newNode;
}
//preNode的后繼指針指向新節(jié)點(diǎn)
preNode.next = newNode;
if (preNode == tail) {//尾部添加元素，更新尾部指針
tail = newNode;
}
}
/**
* 尾部添加元素
*
* @param item
* @return
*/
@Override
public boolean add(T item) {
if (item == null) {
return false;
}
//創(chuàng)建需要插入的結(jié)點(diǎn),并讓其前繼指針指向tail,后繼指針指向tail.next
DNode<T> newNode = new DNode<>(item, tail, tail.next);
//tail的后繼指針指向新節(jié)點(diǎn)
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()) {//數(shù)組越界
throw new IndexOutOfBoundsException();
}
//鏈表中間刪除元素
if (p.next != null) {
p.next.prev = p.prev;
}
p.prev.next = p.next;
//如果是尾節(jié)點(diǎn)則更改tail為p的前驅(qū)節(jié)點(diǎn)
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為尾部節(jié)點(diǎn).更新尾節(jié)點(diǎn)指向,刪除p
tail = p.prev;
tail.next = null;
p.prev = null;
} else {//刪除中間節(jié)點(diǎn)
p.prev.next = p.next;
p.next.prev = p.prev;
}
result = true;
}
p = p.next;//繼續(xù)查找
}
return result;
}
5.讀取和設(shè)置元素。
@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()) {//數(shù)組越界
throw new IndexOutOfBoundsException();
}
if (node != null) {
return node.data;
}
return null;
}
/**
* 設(shè)置元素
*
* @param index
* @param item
* @return
*/
@Override
public T set(int index, T item) {
if (index < 0) {
throw new IndexOutOfBoundsException();
}
if (index >= size()) {//數(shù)組越界
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就是基于雙鏈表實(shí)現(xiàn)幽七，它在此基礎(chǔ)上進(jìn)行了優(yōu)化景殷，具體實(shí)現(xiàn)方法會在后面的LinkedList源碼分析進(jìn)行說明。完整代碼地址:數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)JAVA描述GayHub地址
