1. 双向链表
顾名思义双向链表就是指每个节点都有next指向后驱和prev指向前驱。并且多出了last指针指向尾节点。比如JDK官方的
LinedList就是实现的双向链表。
1.1 方法实现
因为双向链表和单向链表中的要实现的方法基本一致，所以这里直接写实现。
1.1.1 环境变量和内部类
- 环境变量：新增了尾节点last指针
/**
* 链表长度
*/
private int size;
/**
* 头节点
*/
private Node<E> first;
/**
* 尾节点
*/
private Node<E> last;
- 内部类：新增了prev指针和携带pre参数的构造方法。
private static class Node<E>{
E element;
Node<E> next;
Node<E> prev;
public Node(E element){
this.element = element;
}
public Node(E element, Node<E> next){
this.element = element;
this.next = next;
}
public Node(E element, Node<E> next,Node<E> prev){
this.element = element;
this.next = next;
this.prev = prev;
}
@Override
public String toString() {
return "Node{" +
"element=" + element +
'}';
}
}
1.1.2 node()
针对传入的索引位置来判断是从头找还是从尾找。并且
set()和get()方法基于node()来实现也不需要修改。
/**
* 返回index位置的节点
* @param index
* @return
*/
private Node<E> node(int index){
rangeCheck(index);
// 判断传入的index是否大于长度的1/2
if (index < (size >> 1)){
Node<E> node = first;
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.next;
}
return node;
}
}
1.1.3 add()
添加方法除了向头尾节点添加节点之外，只需要找到当前节点即可。
但如果往头尾节点添加时就做出相应的处理。
/**
* 添加元素到index位置
* @param index 位置
* @param e 元素
*/
public void add(int index, E e){
rangeCheckForAdd(index);
// 往尾节点添加
if (index == size){
Node<E> oldLast = last;
this.last = new Node<E>(e,null, last);
// 第一次添加时
if (oldLast == null){
first = last;
}else {
oldLast.next = last;
}
}else {
Node<E> next = node(index);
// 新节点的前驱是原先当前位置的节点的prev
// 新节点的后继是原先当前位置的节点
Node<E> prev = next.prev;
Node<E> newNode = new Node<E>(e, next, prev);
next.prev = newNode;
// 如果往头节点的位置添加，就将新节点作为头节点
if (prev == null) {
first = newNode;
} else {
prev.next = newNode;
}
}
size++;
}
1.1.3 remove()
remov方法也是只需要断开节点的前驱和后继的指向即可。
/**
* 删除index位置的节点
* @param index
* @return
*/
public E remove(int index){
rangeCheck(index);
Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
// 只需要关闭当前节点的引用即可：
// 删除头节点情况：
if (prev == null){
first = next;
}else {
// 让他前驱节点的next指向他的后驱
prev.next = next;
}
// 删除尾节点：
if (next == null){
last = prev;
}else {
// 让他后驱节点的prev指向他的前驱
next.prev = prev;
}
size--;
return node.element;
}
2. 单向循环链表
向较于普通单向链表，在最后的节点处多出了一个next指向头节点。
2.1 方法实现
这部分代码根据上篇博客中的单向链表进行修改。
2.1.1 add()
由于是循环链表，如果往头节点添加元素，需要找到最后一个节点，将它的next指向新的头节点。
/**
* 添加元素到index位置
* @param index 位置
* @param e 元素
*/
public void add(int index, E e){
rangeCheckForAdd(index);
if (index == 0){
Node<E> newFirst = new Node<E>(e,first);
// 找到最后一个节点
// 如果链表是空的，就表示第一个节点的next指向自己。
Node<E> nodeLast = (size == 0) ? newFirst :node(size - 1);
nodeLast.next = newFirst;
first = newFirst;
}else {
Node<E> prev = node(index - 1);
prev.next = new Node<E>(e,prev.next);
}
size++;
}
/**
* 添加元素到链表尾部
* @param e
*/
public void add(E e){
add(size,e);
}
2.1.2 remove()
/**
* 删除index位置的节点
* @param index
* @return
*/
public E remove(int index){
rangeCheck(index);
Node<E> node = first;
if (index == 0){
if (size == 1){
first = null;
}else {
Node<E> nodeLast = node(size - 1);
first = first.next;
nodeLast.next = first;
}
}else {
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}
2.1.3 toString()
因为是循环链表，永远无法找到next为null的节点，所以需要根据size来遍历。
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("LinkedList{list = [");
Node<E> node = first;
int i = 0;
while (i < size){
stringBuilder.append(node.element);
if (i != size - 1){
stringBuilder.append(",");
}
node = node.next;
i++;
}
stringBuilder.append("]").append(",size = ").append(size).append("}");
return stringBuilder.toString();
}
3. 双向循环链表
双向循环链表，比单向循环链表多出了一条first节点的prev指向last节点。
3.1 方法实现
3.1.1 add()
/**
* 添加元素到index位置
* @param index 位置
* @param e 元素
*/
public void add(int index, E e){
rangeCheckForAdd(index);
// 往尾节点添加
if (index == size){
Node<E> oldLast = last;
this.last = new Node<E>(e,first, last);
// 第一次添加时
if (oldLast == null){
first = last;
first.next = first;
first.prev = first;
}else {
oldLast.next = last;
first.prev = last;
}
}else {
Node<E> next = node(index);
// 新节点的前驱是原先当前位置的节点的prev
// 新节点的后继是原先当前位置的节点
Node<E> prev = next.prev;
Node<E> newNode = new Node<E>(e, next, prev);
next.prev = newNode;
prev.next = newNode;
// 如果往头节点的位置添加，就将新节点作为头节点
if (index == 0) {
first = newNode;
}
}
size++;
}
3.1.2 remove()
/**
* 删除index位置的节点
* @param index
* @return
*/
public E remove(int index){
rangeCheck(index);
Node<E> node = first;
E ele = node.element;
if (size == 1){
first = null;
last = null;
}else {
node = node(index);
ele = node.element;
Node<E> prev = node.prev;
Node<E> next = node.next;
// 只需要关闭当前节点的引用即可：
prev.next = next;
next.prev = prev;
// 删除头节点情况：
if (index == 0) {
first = next;
}
// 删除尾节点：
if (index == size - 1) {
last = prev;
}
}
size--;
return ele;
}
3.1.3 toString()
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("LinkedList{list = [");
Node<E> node = first;
int i = 0;
while (i < size){
stringBuilder.append(node.element);
if (i != size - 1){
stringBuilder.append(",");
}
node = node.next;
i++;
}
stringBuilder.append("]").append(",size = ").append(size).append("}");
return stringBuilder.toString();
}