LinkedList介绍
还是老样子，摘取java1.8api文档（谷歌翻译版）中对LinkedList的介绍
双链表实现了
List和Deque接口。 实现所有可选列表操作，并允许所有元素（包括null）。所有的操作都能像双向列表一样预期。 索引到列表中的操作将从开始或结束遍历列表，以更接近指定的索引为准。
好吧。。。又是字都认识但合在一起读不懂系列，机器翻译就不能人性化一点吗？？？
我理解的LinkedList是下面这样的
LinkedList是一个双向链表结构，每一个Node对象维护了前驱和后继节点，它能够从开始节点正向遍历，同时也能从结束节点反向遍历，且内部提供了丰富的方法使其能够方便的对链表进行操作。
LinkedList定义
了解完LinkedList作用后，接下来我们来定义它的成员变量与基本方法
成员变量与其内部类
// 元素个数
private int size = 0;
// 静态内部类 Node<E>
private static class Node<E> {
// 元素值
E item;
// 后继节点
Node<E> next;
// 前驱节点
Node<E> prev;
Node(Node<E> prev, Node<E> next, E element) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// 记录首节点与尾节点方便前后遍历
Node<E> first;
Node<E> last;基本方法
/**
* 将元素置于链表头部
*
* @param e 待添加元素
*/
public void linkFirst(E e) {
}
/**
* 将元素置于链表尾部
*
* @param e 待添加元素
*/
public void linkLast(E e) {// 记录原始尾节点
}
/**
* 将元素插入指定节点之前
*
* @param e 待插入元素
* @param succ 指定节点
*/
public void linkBefore(E e, Node<E> succ) {
}
/**
* 移除链表首节点
*
* @param f 待移除节点
* @return 移除节点值
*/
public E unlinkFirst(Node<E> f) {
return null;
}
/**
* 移除链表尾节点
*
* @param l 待移除节点
* @return 移除节点值
*/
public E unlinkLast(Node<E> l) {
return null;
}
/**
* 移除指定节点（非空）
*
* @param e 待移除节点
* @return 待移除节点值
*/
public E unlink(Node<E> e) {
return null;
}
/**
* 获取链表的头节点
*
* @return 返回头节点值
*/
public E getFirst() {
return null;
}
/**
* 获取链表的尾节点
*
* @return 返回尾节点值
*/
public E getLast() {
return null;
}
/**
* 返回指定元素在链表中的索引
*
* @param o 待查找元素
* @return 返回索引值 未找到返回 -1
*/
public int indexOf(Object o) {
return 0;
}
/**
* 返回指定索引处的节点对象
*
* @param index 指定索引值
* @return 节点对象
*/
public Node<E> node(int index) {
return null;
}
/**
* 清空链表
*/
public void clear() {
}方法细节
/**
* 将元素置于链表头部
*
* @param e 待添加元素
*/
public void linkFirst(E e) {
// 记录原始头节点
Node<E> f = first;
// 通过元素 e 构造Node对象
Node<E> newNode = new Node<>(null, f, e);
// 将first变更为新节点
first = newNode;
// 判断原始头节点是否为空
if (f == null) {
// 若为空则将last变更为新节点
last = newNode;
} else {
// 若不为空则将原始头节点的前驱节点指向新节点
f.prev = newNode;
}
size++;
}
/**
* 将元素置于链表尾部
*
* @param e 待添加元素
*/
public void linkLast(E e) {
// 记录原始尾节点
Node<E> l = last;
// 通过元素 e 构造Node对象
Node<E> newNode = new Node<>(l, null, e);
// 将last变更为新节点
last = newNode;
// 判断原始尾节点是否为空
if (l == null) {
// 若为空则将first变更为新节点
first = newNode;
} else {
// 若不为空则将原始尾节点的后继节点指向新节点
l.next = newNode;
}
size++;
}
/**
* 将元素插入指定节点之前
*
* @param e 待插入元素
* @param succ 指定节点
*/
public void linkBefore(E e, Node<E> succ) {
// 记录指定节点的前驱节点
Node<E> pred = succ.prev;
Node<E> newNode = new Node<>(pred, succ, e);
// 将指定节点的prev域指向新节点
succ.prev = newNode;
// 判断指定节点的前驱节点是否为空
if (pred == null) {
// 若为空则当前插入节点设为first
first = newNode;
} else {
// 若不为空将指定节点的前驱节点的后继节点指向新节点(有点绕口。。。尽力理解)
pred.next = newNode;
}
size++;
} /**
* 移除链表首节点
*
* @param f 待移除节点
* @return 移除节点值
*/
public E unlinkFirst(Node<E> f) {
// 记录待移除节点值
E element = f.item;
// 记录待移除节点后继节点
Node<E> next = f.next;
// 移除节点值与后继节点置为null
f.item = null;
f.next = null;
// 变更头节点
first = next;
// 判断头节点是否为空
if (next == null) {
// 若为空则将尾节点也置空
last = null;
} else {
// 若不为空则将头节点的前驱节点置空
next.prev = null;
}
size--;
return element;
}
/**
* 移除链表尾节点
*
* @param l 待移除节点
* @return 移除节点值
*/
public E unlinkLast(Node<E> l) {
// 记录待移除节点值
E element = l.item;
// 记录待移除节点前驱节点
Node<E> pred = l.prev;
// 移除节点值与前驱节点置为null
l.item = null;
l.prev = null;
// 变更尾节点
last = pred;
// 判断尾节点是否为空
if (pred == null) {
// 若为空则将头节点也置空
first = null;
} else {
// 若不为空则将尾节点的后继节点置空
pred.next = null;
}
size--;
return element;
}
/**
* 移除指定节点（非空）
*
* @param e 待移除节点
* @return 待移除节点值
*/
public E unlink(Node<E> e) {
// 记录待删除节点值
E element = e.item;
// 记录待删除节点的前驱和后继节点
Node<E> next = e.next;
Node<E> prev = e.prev;
// 判断前驱节点是否为空
if (prev == null) {
// 若为空则将头节点置换
first = next;
} else {
// 若不为空则将待删除节点的前驱节点的next域指向待删除节点的后继节点
prev.next = next;
// 将待删除节点的prev域置空
e.prev = null;
}
// 判断后继节点是否为空
if (next == null) {
// 若为空则将尾节点置换
last = prev;
} else {
// 若不为空则将待删除节点的后继节点的prev域指向待删除节点的前驱节点
next.prev = prev;
// 将待删除节点的next域置空
e.next = null;
}
e.item = null;
size--;
return element;
} /**
* 移除链表尾节点
*
* @param l 待移除节点
* @return 移除节点值
*/
public E unlinkLast(Node<E> l) {
// 记录待移除节点值
E element = l.item;
// 记录待移除节点前驱节点
Node<E> pred = l.prev;
// 移除节点值与前驱节点置为null
l.item = null;
l.prev = null;
// 变更尾节点
last = pred;
// 判断尾节点是否为空
if (pred == null) {
// 若为空则将头节点也置空
first = null;
} else {
// 若不为空则将尾节点的后继节点置空
pred.next = null;
}
size--;
return element;
}
/**
* 移除指定节点（非空）
*
* @param e 待移除节点
* @return 待移除节点值
*/
public E unlink(Node<E> e) {
// 记录待删除节点值
E element = e.item;
// 记录待删除节点的前驱和后继节点
Node<E> next = e.next;
Node<E> prev = e.prev;
// 判断前驱节点是否为空
if (prev == null) {
// 若为空则将头节点置换
first = next;
} else {
// 若不为空则将待删除节点的前驱节点的next域指向待删除节点的后继节点
prev.next = next;
// 将待删除节点的prev域置空
e.prev = null;
}
// 判断后继节点是否为空
if (next == null) {
// 若为空则将尾节点置换
last = prev;
} else {
// 若不为空则将待删除节点的后继节点的prev域指向待删除节点的前驱节点
next.prev = prev;
// 将待删除节点的next域置空
e.next = null;
}
e.item = null;
size--;
return element;
} /**
* 获取链表的头节点
*
* @return 返回头节点值
*/
public E getFirst() {
Node<E> f = first;
if (f == null) {
throw new NoSuchElementException("节点不存在");
}
return f.item;
}
/**
* 获取链表的尾节点
*
* @return 返回尾节点值
*/
public E getLast() {
Node<E> l = last;
if (l == null) {
throw new NoSuchElementException("节点不存在");
}
return l.item;
} /**
* 返回指定元素在链表中的索引
*
* @param o 待查找元素
* @return 返回索引值 未找到返回 -1
*/
public int indexOf(Object o) {
// 记录索引位置
int index = 0;
// 判断查找元素是否为空
if (o == null) {
// 为空
// cur 指向头节点
Node<E> cur = first;
// 从头节点开始遍历
while (cur != null) {
// 直到找到item == null 返回
if (cur.item == null) {
return index;
}
// 索引值递增
index++;
cur = cur.next;
}
} else {
// 不为空也是同样遍历，找到item == 指定元素值返回
Node<E> cur = first;
while (cur != null) {
if (o.equals(cur.item)) {
return index;
}
index++;
cur = cur.next;
}
}
return -1;
}
/**
* 返回指定索引处的节点对象
*
* @param index 指定索引值
* @return 节点对象
*/
public Node<E> node(int index) {
// 判断传入索引是否大于节点数量的一半
if (index < (size >> 1)) {
// 若小于一半则正序遍历
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
} else {
// 大于一半则倒序遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
}
/**
* 清空链表
*/
public void clear() {
// 遍历链表，所有节点置空
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = null;
last = null;
size = 0;
}通过以上方法我们能体会到双链表的奥秘所在是把握住Node节点的prev与next域的连接与断开，使用画图可以更加直观的体会到方法过程。
测试案例
为了测试方便，我编写了两个打印方法，如下：
private static void print(Mini_LinkedList<String> linkedList) {
int size = linkedList.getSize();
for (int i = 0; i < size; i++) {
Mini_LinkedList.Node<String> node = linkedList.node(i);
if (node != null && node.prev != null && node.next != null) {
System.out.println(node.prev.item + " <==> " + node.item + " <==> " + node.next.item);
} else if (node != null && node.prev != null) {
System.out.println(node.prev.item + " <==> " + node.item + " <==> " + "null");
} else if (node != null && node.next != null) {
System.out.println("null" + " <==> " + node.item + " <==> " + node.next.item);
}
}
}
private static void print2(Mini_LinkedList.Node<String> node) {
if (node != null && node.prev != null && node.next != null) {
System.out.println(node.prev.item + " <==> " + node.item + " <==> " + node.next.item);
} else if (node != null && node.prev != null) {
System.out.println(node.prev.item + " <==> " + node.item + " <==> " + "null");
} else if (node != null && node.next != null) {
System.out.println("null" + " <==> " + node.item + " <==> " + node.next.item);
}
} @Test
public void linkFirst() {
Mini_LinkedList<String> stringMini_linkedList = new Mini_LinkedList<>();
stringMini_linkedList.linkFirst("hello");
stringMini_linkedList.linkFirst("hello1");
stringMini_linkedList.linkFirst("hello2");
print(stringMini_linkedList);
/*
null <==> hello2 <==> hello1
hello2 <==> hello1 <==> hello
hello1 <==> hello <==> null
*/
}
@Test
public void linkLast() {
Mini_LinkedList<String> stringMini_linkedList = new Mini_LinkedList<>();
stringMini_linkedList.linkLast("hello");
stringMini_linkedList.linkLast("hello1");
stringMini_linkedList.linkLast("hello2");
print(stringMini_linkedList);
/*
null <==> hello <==> hello1
hello <==> hello1 <==> hello2
hello1 <==> hello2 <==> null
*/
}
@Test
public void linkBefore() {
Mini_LinkedList<String> stringMini_linkedList = new Mini_LinkedList<>();
stringMini_linkedList.linkLast("hello");
stringMini_linkedList.linkLast("hello1");
stringMini_linkedList.linkLast("hello2");
Mini_LinkedList.Node<String> first = stringMini_linkedList.first;
stringMini_linkedList.linkBefore("hello4", first);
print(stringMini_linkedList);
/*
null <==> hello4 <==> hello
hello4 <==> hello <==> hello1
hello <==> hello1 <==> hello2
hello1 <==> hello2 <==> null
*/
}
@Test
public void unlinkFirst() {
Mini_LinkedList<String> stringMini_linkedList = new Mini_LinkedList<>();
stringMini_linkedList.linkLast("hello");
stringMini_linkedList.linkLast("hello1");
stringMini_linkedList.linkLast("hello2");
Mini_LinkedList.Node<String> first = stringMini_linkedList.first;
stringMini_linkedList.unlinkFirst(first);
print(stringMini_linkedList);
/*
null <==> hello1 <==> hello2
hello1 <==> hello2 <==> null
*/
}
@Test
public void unlinkLast() {
Mini_LinkedList<String> stringMini_linkedList = new Mini_LinkedList<>();
stringMini_linkedList.linkLast("hello");
stringMini_linkedList.linkLast("hello1");
stringMini_linkedList.linkLast("hello2");
Mini_LinkedList.Node<String> last = stringMini_linkedList.last;
stringMini_linkedList.unlinkLast(last);
print(stringMini_linkedList);
/*
null <==> hello <==> hello1
hello <==> hello1 <==> null
*/
}
@Test
public void unlink() {
Mini_LinkedList<String> stringMini_linkedList = new Mini_LinkedList<>();
stringMini_linkedList.linkLast("hello");
stringMini_linkedList.linkLast("hello1");
stringMini_linkedList.linkLast("hello2");
Mini_LinkedList.Node<String> first = stringMini_linkedList.first;
stringMini_linkedList.unlink(first);
print(stringMini_linkedList);
/*
null <==> hello1 <==> hello2
hello1 <==> hello2 <==> null
*/
}
@Test
public void indexOf() {
Mini_LinkedList<String> stringMini_linkedList = new Mini_LinkedList<>();
stringMini_linkedList.linkLast("hello");
stringMini_linkedList.linkLast("hello1");
stringMini_linkedList.linkLast("hello2");
int index = stringMini_linkedList.indexOf("hello1");
System.out.println("索引：" + index);
/*
索引：1
*/
}
@Test
public void node() {
Mini_LinkedList<String> stringMini_linkedList = new Mini_LinkedList<>();
stringMini_linkedList.linkLast("hello");
stringMini_linkedList.linkLast("hello1");
stringMini_linkedList.linkLast("hello2");
Mini_LinkedList.Node<String> node = stringMini_linkedList.node(1);
print2(node);
/*
hello <==> hello1 <==> hello2
*/
}
@Test
public void clear() {
Mini_LinkedList<String> stringMini_linkedList = new Mini_LinkedList<>();
stringMini_linkedList.linkLast("hello");
stringMini_linkedList.linkLast("hello1");
stringMini_linkedList.linkLast("hello2");
stringMini_linkedList.clear();
print(stringMini_linkedList);
/*
null
*/
}总结
通过构建自己的ArrayList和LinkedList，我们不难发现它两还是有很大的区别
数据结构上的不同
- ArrayList底层是基于动态数组实现，而LinkedList是通过内置Node类的prev、next域交织在一起，故ArrayList元素间没有交集而LinkedList元素间关联性强
效率上的不同
- ArrayList能在O(1)时间获取到指定索引值，而LinkedList要通过正序或倒序遍历来获取，时间复杂度为O(n)
- ArrayList删除元素时需移动数组元素（删除尾元素例外），而LinkedList只需改变prev、next指向即可
空间占用上的不同
- ArrayList有扩容机制，需要预留空间。而LinkedList随来随用，但维护prev、next域需要占用一定空间。
相信大家在看完它们的区别后能在合适的工作场景去合理选择使用~