java.util.LinkedList类

java.util.LinkedList类


底层数据结构

LinkedList底层是一个实现了ListDeque接口的双链表

  • 增删快,查询慢
  • 非线程安全

API

1.构造函数

  1. 空构造函数:public LinkedList()
  2. 用已有集合创建链表的构造函数:public LinkedList(Collection<? extends E> c)
1
2
3
4
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

2.add():插入一个元素

  1. 尾插:public boolean add(E e)
1
2
3
4
public boolean add(E e) {
linkLast(e); //尾插
return true;
}

尾插法:

1
2
3
4
5
6
7
8
9
10
11
12
//尾插
void lastLink(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. 在指定位置插入元素(性能不高):public void add(int index, E element)
1
2
3
4
5
6
7
public void add(int index, E element) {
checkPositionIndex(index); //检查索引是否在[0,size]之间
if (index == size)
linkLast(element); //尾插
else
linkBefore(element, node(index)); //链表中部插入,性能差
}

3.addAll():插入一个集合

  1. public boolean addAll(Collection c):尾插一个集合
1
2
3
public boolean addAll(Collection c) {
return addAll(size, c);
}
  1. public boolean addAll(int index, Collection<? extends E> c):指定位置插入一个集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); //检查索引是否在[0,size]之间
Object[] a = c.toArray(); //集合转数组
int numNew = a.length;
if (numNew == 0) return false; //插入集合为空,直接返回false

//索引位置的前驱和后继节点
Node<E> pred, succ;
//插入位置在尾部
if (index == size) {
succ = null;
pred = last;
}
//否则,调用node()获得后继节点
else{
succ = node(index);
pred = succ.prev;
}
//forEach,迭代器遍历到指定位置,插入数据
for(Object o : a) {
@SuppressWarnings("unchecked") E e = (E)o;
//创建新节点
Node<E> newNode = new Node<E>(pred, e, null);
//如果插入链表为空
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//如果插入位置在尾部,重置last节点
if(succ == null)
last = pred;
else{ //否则将插入的链表和原链表串联起来
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}

4.addFirst():头插

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void addFirt(E e) {
linkFirst(e);
}

private void linkFirst(E e) {
final Node<E> f = first;
//创建新节点,以头节点为后继节点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
//空链表
if(f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}

5.addLast():尾插

1
2
3
public void addLast(E e) {
linkLast(e);
}

6.public E get(int index):根据索引返回数据

1
2
3
4
5
6
public E get(int index) {
//检查index是否在[0,size]内
checkElementIndex(index);
//找index对应的节点,返回数据
return node(index).item;
}

7.获取头节点数据

  1. public E getFirst()如果链表为空,直接抛出异常
1
2
3
4
5
6
public E getFirst(){
final Node<E> f = first;
if(f == null)
throw new NoSuchElementException();
return f.item;
}
  1. public E element()如果链表为空,直接抛出异常
1
2
3
public E element(){
return getFirst();
}
  1. public E peek()如果链表为空,返回null
1
2
3
4
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
  1. public E peekFirst()如果链表为空,返回null
1
2
3
4
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}

8.获取尾节点数据

  1. public E getLast()如果链表为空,直接抛出异常
1
2
3
4
5
6
public E getLast() {
final Node<E> l = last;
if(l == null)
throw new NoSuchElementException();
return l.item;
}
  1. public E peekLast()如果链表为空,返回null
1
2
3
4
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}

9.public int indexOf(Object o):从头遍历,返回元素首次出现索引,如果找不到返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int indexOf(Object o) {
int index = 0;
//从头遍历
if(o == null){
for(Node<E> x = first; x != null; x = x.next){
if (x.item == null) //null
return index;
index++;
}
}else{
for(Node<E> x = first; x != null; x = x.next){
if (o.equals(x.item))
return index;
index++;
}
}
return -1; //如果找不到,返回-1
}

10.public int lastIndexOf(Object o):从尾遍历,返回元素最后出现索引,如果找不到返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int lastIndexOf(Object o) {
int index = size;
//从尾遍历
if(o == null){
for(Node<E> x = last; x != null; x = x.prev){
index--;
if(x.item == null) //null
return index;
}
}else{
for(Node<E> x = last; x != null; x = x.prev){
index--;
if(o.equals(x.item))
return index;
}
}
return -1; //如果找不到,返回-1
}

11.public boolean contains(Object o):是否含有指定元素

1
2
3
public boolean contains(Object o) {
return indexOf(o) != -1;
}

12.删除头节点(空链表抛出异常)

  1. public E remove()
1
2
3
public E remove() {
return removeFirst();
}
  1. public E pop()
1
2
3
public E pop() {
return removeFirst();
}
  1. public E removeFirst()
1
2
3
4
5
6
public E removeFirst() {
final Node<E> f = first;
if(f == null)
return new NoSuchElementException(); //空链表抛出异常
return unlinkFirst(f);
}

13.删除尾节点

  1. public E removeLast()空链表抛出异常
1
2
3
4
5
6
public E removeLast(){
final Node<E> l = last;
if(l == null)
return new NoSuchElementException();
return unlinkLast(l);
}
  1. public E pollLast()空链表返回null
1
2
3
4
public E pollLast(){
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}

14.public boolean remove(Object o):删除指定元素

如果指定元素不存在,返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public boolean remove(Object o) {
//如果删除对象为null
if (o == null) {
//从头开始遍历
for (Node<E> x = first; x != null; x = x.next) {
//找到元素
if (x.item == null) { //null
//从链表中移除找到的元素
unlink(x);
return true;
}
}
} else {
//从头开始遍历
for (Node<E> x = first; x != null; x = x.next) {
//找到元素
if (o.equals(x.item)) {
//从链表中移除找到的元素
unlink(x);
return true;
}
}
}
return false;
}

//从链表中断开指定节点,调用方需要保证指定节点不是null
E unlink(Node<E> x) {
//在调用方需要指定节点不是null
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++;
retrun element;
}

15.public E remove(int index):删除指定位置元素

1
2
3
4
5
6
public E remove(int index) {
//检查index范围
checkElementIndex(index);
//将节点删除
return unlink(node(index));
}
-------------本文结束感谢您的阅读-------------

本文标题:java.util.LinkedList类

文章作者:DragonBaby308

发布时间:2019年08月25日 - 17:46

最后更新:2019年09月22日 - 10:09

原始链接:http://www.dragonbaby308.com/java-util-LinkedList/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

急事可以使用右下角的DaoVoice,我绑定了微信会立即回复,否则还是推荐Valine留言喔( ఠൠఠ )ノ
0%