转载

JAVA基础整理（五）

LinkedList类

链表容器也是通过对比jdk源码进行对比学习。

1.定义结点类型

class Node<E>{

E item;
Node<E> next;
Node<E> prev;

Node(Node<E>prev,E item,Node<E>next){
    this.prev=prev;
    this.next=next;
    this.item=item;
}
Node(E item){
    this.item=item;
}

}

private static class Node<E> {

E item;
Node<E> next;
Node<E> prev;

Node(Node<E> prev, E element, Node<E> next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
}

}

分析：

（1）Node的访问权限是private的，因为这这是链表内部使用的结点类。

（2）一开始不理解结点的构造函数为什么要传入prev和next，但其实就是结点的最简单的全参构造，不知道时传null即可，等结点插入链表时再赋值即可。

2.增加一个结点（不带index，直接尾插法）

public void add(Node<E> node){

if(first==null){//当链表里没有一个元素时，头尾都是该结点，并且该结点的前后都是空的。
    first=node;
    last=node;
    node.prev=null;
    node.next=null;
}
else {//尾结点是该结点的前驱结点，该结点是尾节点的后继结点，更新尾节点。
    node.prev=last;
    last.next=node;
    last=node;
}
    size++;//链表长度增加。

}

增加一个结点的步骤(这里都只考虑尾插法)：

1.如果是第一个结点，把它同时给first和last，并且这个结点的前后都是空。

2.如果不是第一个结点，先把链表中的last给这个结点的前驱，把这个结点给链表里last的后继，然后更新链表里的last结点为当前的node。

void linkLast(E e) {

final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
    first = newNode;
else
    l.next = newNode;
size++;
modCount++;

}

（1）插入时传入的应该是数据，把数据封装成结点的事应该让内部去做（这也就是解释了一开始自己的疑惑，源码的第二行封装结点时就是前驱传入了链表的last，后继传了null）

（2）其余逻辑差别不大。

3.删除一个结点（带index）

public void delete(int index){

size--;
Node<E> current=first;
for(int i=1;i<=index-1;i++){
    current = current.next;
}
if(current.equals(first)){
    first=current.next;
}
if (current.equals(last)){
    last=current.prev;
}
else {
    current.prev.next = current.next;
    current.next.prev = current.prev;
}

}

（都暂不考虑范围问题）

分析：头尾位置单独考虑，其余位置指针指向对应改变即可。

E unlink(Node<E> x) {

final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;

if (prev == null) {
    first = next;
} else {
    prev.next = next;
    x.prev = null;
}

if (next == null) {
    last = prev;
} else {
    next.prev = prev;
    x.next = null;
}

x.item = null;
size--;
modCount++;
return element;

}

逻辑基本相同，此外，删除时有这么个操作

f.item = null;
f.next = null; // help GC

help gc 的小方针。

4.修改一个结点的数据

（1）遍历找到这个index结点

（2）修改item即可

5.查找指定数据

（1）遍历找到这个index结点

（2）拿出item

<h3>Vector 线程安全的，实现与arraylist类似，只是加了个线程安全，但是带来的效率低。</h3>

原文 https://segmentfault.com/a/1190000019193320

正文到此结束

所属分类：编程技术 Java

本文标签： 数据 LinkedList 安全 id 线程删除 http https final node list 源码遍历 equals CTO ArrayList
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

JAVA基础整理（五）

LinkedList类

链表容器也是通过对比jdk源码进行对比学习。

1.定义结点类型

分析：

2.增加一个结点（不带index，直接尾插法）

增加一个结点的步骤(这里都只考虑尾插法)：

3.删除一个结点（带index）

分析：头尾位置单独考虑，其余位置指针指向对应改变即可。

4.修改一个结点的数据

5.查找指定数据

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流