單鏈表(可以用來實(shí)現(xiàn)棧和隊(duì)列)
private class Node {
/**
* 鏈表存儲(chǔ)的數(shù)據(jù)(泛型)
*/
Item item;
/**
* 指向下一個(gè)節(jié)點(diǎn)的指針
*/
Node next;
}
刪除鏈表的元素
image.png
添加元素
image.png
雙向鏈表(實(shí)現(xiàn)LinkedList)
/**
* 鏈表節(jié)點(diǎn)
* @param <AnyType>
*/
private static class Node<AnyType> {
/**
* @param d 數(shù)據(jù)
* @param p 上一個(gè)節(jié)點(diǎn)
* @param n 下一個(gè)節(jié)點(diǎn)
*/
public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) {
data = d;
prev = p;
next = n;
}
/**
* 數(shù)據(jù)
*/
public AnyType data;
/**
* 上一個(gè)節(jié)點(diǎn)
*/
public Node<AnyType> prev;
/**
* 下一個(gè)節(jié)點(diǎn)
*/
public Node<AnyType> next;
}
image.png
添加元素
image.png
/**
* 向目標(biāo)元素p之前插入x
*
* @param p 目標(biāo)p
* @param x 插入的元素
*/
private void addBefore(Node<AnyType> p, AnyType x) {
/*構(gòu)建一個(gè)新node,prev是p.prev,next是p 1,3*/
Node<AnyType> newNode = new Node<>(x, p.prev, p);
/*新node的上一個(gè)節(jié)點(diǎn)的next 指向自己 2*/
newNode.prev.next = newNode;
/*p的prev 指向自己 4*/
p.prev = newNode;
theSize++;
modCount++;
}
刪除元素
image.png
/**
* 刪除目標(biāo)節(jié)點(diǎn)
*
* @param p 目標(biāo)節(jié)點(diǎn)
* @return 刪除的數(shù)據(jù)
*/
private AnyType remove(Node<AnyType> p) {
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
modCount++;
return p.data;
}
