java链表LinkedList类
/**
* List接口的实现类LinkedList linked list链表
* ArrayList和Vector都是使用数组来存储数据 数组是空间连续的 在内存中指定长度创建连续的空间 数组的元素与元素之间在空间上是相邻的
* 数组使用index索引所以查询效率高O(1) 但每次增删都涉及到index后面元素的位移 增删效率低
* LinkedList使用双向链表存储数据 每个结点/元素包含数据域(即元素本身的数据)和指针域(指向直接前驱结点和指向直接后继结点的两个指针)
* 链表不记录index 每次查询需要从表头结点或表尾结点沿指针域逐个结点查找 查询效率低 但每次增删只需要更改目标位置前后结点的指针域 不需要对元素进行移位 增删效率高
* LinkedList线程不安全
*/
public class TestLinkedList {
public static void main(String[] args) {
List<String> linked = new LinkedList<>();
//LinkedList实现了List的抽象方法 对于List的方法的调用通过List引用变量来使用 //linked.add();linked.remove();linked.clear();linked.size();linked.toArray();linked.indexOf();linked.set();linked.get();linked.contains();linked.isEmpty(); LinkedList实现的这些基本方法的用法同ArrayList和Vector
LinkedList<String> ll1 = new LinkedList<>();
//测试LinkedList类内定义的用于链表操作的方法 这些方法不是实现自List 不能用List引用变量调用
ll1.addFirst("a");
//.addFirst()向链表的表头添加结点 每次添加的结点都变更为表头结点
ll1.addFirst("b");
ll1.addFirst("c");
System.out.println(ll1);
//结果为[c, b, a] 每次addFirst的结点都变更为表头
ll1.addLast("d");
//.addLast()向表尾添加结点 每次添加都变更为新的表尾
ll1.addLast("f");
for (String e:ll1){
System.out.print(e+",");
//结果c,b,a,d,f,
}
System.out.println();
System.out.println(ll1.getFirst());
//.getFirst()返回表头结点 结果为c
System.out.println(ll1.getLast());
//.getLast()返回表尾结点 结果为f
System.out.println(ll1.removeFirst());
System.out.println(ll1);
//.removeFirst()删除表头并返回 删除了c并返回 链表的结果[b, a, d, f]
System.out.println(ll1.removeLast());
for (int i = 0 ;i<ll1.size();i++){
System.out.print(ll1.get(i)+",");
}
//.removeLast()删除表尾并返回 删除了f并返回 链表的结果[b, a, d]
System.out.println();
System.out.println(ll1.pop());
//作用同Stack栈容器的pop() 弹出栈顶/表头结点 并返回 相当于removeFirst
System.out.println(ll1);
//结果[a, d]
ll1.push("g");
//作用同Stack栈容器的push() 压栈 将结点推入栈顶/表头 相当于addFirst
System.out.println(ll1);
//结果[g, a, d]
/* LinkedList通过双向链表存储数据 源码
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
//泛型类
private static class Node<E> {
//node结点 static class 静态内部类 在LinkedList类内部定义
E item;
Node<E> next;
Node<E> prev;
//item用来保存元素 即数据域 next/previous指针域指向直接后继结点和直接前驱结点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
//没有无参构造器 每个结点在实例时必须定义唯三的属性 表头结点的prev=null 表尾结点的next=null
}
//回到LinkedList类内
transient int size = 0;
//size即结点的总数 作用同ArrayList/Vector.size
transient Node<E> first;
transient Node<E> last;
//LinkedList对象中只保存表头结点first和表尾结点last
public boolean add(E e) {
linkLast(e);
return true;
}
//实现List的add()方法 通过向表尾添加结点的方式
void linkLast(E e) {
final Node<E> l = last;
//先将当前表尾缓存 如果链表为空则last=null
final Node<E> newNode = new Node<>(l, e, null);
//l赋值给prev e赋值给item next设为null
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
//新结点变为表尾结点，如果链表为空则将first和last都设为新结点 否则将缓存的原表尾结点.next链到新结点
size++;
modCount++;
}
//每个结点保存前后的指针 LinkedList容器保存头尾的指针 这样做不会在链表容器内保存每一个结点的指针
public void addFirst(E e) {linkFirst(e);}
//linkFirst和linkLast原理相同 一个在表头做调整 一个在表尾做调整 操作基本是镜像的 这里addFirst没有返回值 普通add会返回boolean
public void add(int index, E element) {
checkPositionIndex(index);
//判定索引越界
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//判断index==size即向表尾添加结点所以直接调用linkLast() 也同时解决了index=size=0空链表的情况 所以else为链表中至少有一个结点的情况 node(index)方法如下
Node<E> node(int index) {
if (index < (size >> 1)) {
//二分 size即length /2为中位 size为偶数时/2是右半边的首位 小于中位则从头查找更快 大于则从尾查找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
//将表头赋值给x 每次.next都会返回直接后继结点 从first一直.next.next.next可以通到last 当i=index-1时x.next即为index位结点
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//node(index)是查找索引位结点的方法 linkBefore(element, node(index))方法如下
void linkBefore(E e, Node<E> succ) {
//传入的succ即为index位结点
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
//通过index位结点succ找到直接前驱结点pred new新结点.prev设为前驱结点 .next设为succ 将succ的prev和前驱结点的next改为新结点
//pred==null即add(0,element)的情况
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//node()方法返回Node结点 .item即数据域/存放的元素 get()方法返回的是结点的数据，类型<E>，返回的不是结点Node<E>
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//移除index位结点 先node()返回index位的结点再解除链接unlink()方法如下
E unlink(Node<E> x) {
//泛型方法 根据传入的结点类型做调整
final E element = x.item;
//缓存要删除结点x的元素作为之后的返回值
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
//prev==null即remove(0) 将first=x改为next
first = next;
} else {
prev.next = next;
x.prev = null;
}
//将前驱结点跳过x链到后继结点
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
//将指向x的链接全部撤掉 将x的指针全赋null 将x的item赋null x对象和数据对象不再被引用 等待垃圾回收
size--;
modCount++;
return element;
}
public boolean remove(Object o) {
if (o == null) {
//元素/数据虽然是空 但.item保存空元素的结点是存在的 结点的prev/next可能有值 即空数据结点占了一位
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
//将迭代通过.next.next实现 表尾结点的next为null 所以直到遇到null即遍历完成 这里x=null是判断结点不是上面的x.item=null判断元素 结点只有空链表或表头.prev或表尾.next才会为空
if (o.equals(x.item)) {
//这里调用了o.equals()方法，如果没有单独判断if(o==null)的话，当o为null时调用方法会报空指针异常
unlink(x);
return true;
}
}
}
return false;
//不存在o返回false
}
*/
}
}
