内功心法 -- java.util.LinkedList (1)

时间:2022-07-17 17:38:20

写在前面的话:读书破万卷,编码如有神
--------------------------------------------------------------------
下文主要对java.util.LinkedList<E>进行整体性介绍,主要内容包括:

1、 LinkedList概述

2、 LinkedList中的属性、构造方法、常用方法介绍

3、 LinkedList遍历

参考内容:

1、JDK源码(1.7)

--------------------------------------------------------------------

1、LinkedList概述                                                               

java.util.LinkedList<E>是一个什么玩意儿? 它有什么功能? 我们拿LinkedList能够做什么?

简单点说: java.util.LinkedList<E>是一个链表,它是用来存放其他Java对象的,内部是通过链表的形式实现的

先看下面的图(简略图):

内功心法 -- java.util.LinkedList (1)

(1) java.util.LinkedList<E>是一个链表,用来存放其它java对象的,只要是java对象就可以往LinkedList里面放。

(2) java.util.LinkedList<E>内部是通过链表来实现的,它实现了所有的列表操作,并且运行插入所有元素(包括null)。

(3) java.util.LinkedList<E>可以用作 堆栈、队列、双端队列、单向链表、双向链表

java.util.LinkedList<E>的定义如下:

 1 public class LinkedList<E>
 2     extends AbstractSequentialList<E>
 3     implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
 4 
 5     //fields
 6    
 7     //constructor
 8 
 9     //methods
10 
11     //inner class 'ListItr'、'DescendingIterator'
12 
13     //inner class 'Node'  
14 }

从LinkedList类的定义中可以看到,它好复杂哟,定义了那么多的东西,又有父类,又实现了接口等等,这都要怪它的'祖宗',定义了那么多的规范、规则。(@_@)

好了,不多废话,撸起袖子继续干:

下面来看看一副图:

内功心法 -- java.util.LinkedList (1)

--------------------------------------------------------------------

2、 LinkedList中的属性、构造方法、常用方法介绍                       

2、1 java.util.LinkedList<E>中的常见属性

 1 //双端队列中节点个数
 2 transient int size = 0;
 3 
 4 //始终指向双端队列中第一个节点
 5 transient Node<E> first;
 6 
 7 //始终指向双端队列中最后一个节点
 8 transient Node<E> last;
 9 
10 //序列号
11 private static final long serialVersionUID = 876323262645176354L;
12 
13 //fast-fail失败机制
14 protected transient int modCount = 0;

2、2 java.util.LinkedList<E>中链表节点数据类型

 1    /*
 2      描述双端队列中节点数据类型
 3    */ 
 4    private static class Node<E> {
 5         //节点值
 6         E item;
 7         //指向下一个节点
 8         Node<E> next;
 9         //指向上一个节点
10         Node<E> prev;
11      
12         //构造函数
13         Node(Node<E> prev, E element, Node<E> next) {
14             this.item = element;
15             this.next = next;
16             this.prev = prev;
17         }
18     }

2、3 java.util.LinkedList<E>中构成方法

第一种: 默认构造方法(无参数构造方法)

1 public LinkedList()

第二种: 带初始化子列表参数的构造方法

1 public LinkedList(Collection<? extends E> c)

2、4 java.util.LinkedList<E>中常用方法

      队头、尾操作 E getFirst()  获取,但不移除此双端队列的第一个元素
 E getLast()  获取,但不移除此双端队列的最后一个元素
E removeFirst()  获取并移除此双端队列第一个元素
E removeLast()  获取并移除此双端队列的最后一个元素
void addFirst(E e)  将指定元素插入此双端队列的开头
void addLast(E e)  将指定元素插入此双端队列的末尾
     修改操作 boolean add(E e)  

将指定元素插入此双端队列的尾部

boolean remove(Object o) 移除此双端队列中的元素o
boolean addAll(Collection<? extends E> c)  将子集合c中的全部插入到此双端队列的尾部
boolean addAll(int index, Collection<? extends E> c)  将子集合c中的全部插入到此双端队列的index开始位置
void clear()  将此双端队列中的元素节点全部清空
    位置访问操作 E get(int index)  返回此双端队列中index位置上的节点
E set(int index, E element)  将此双端队列中index位置上的节点替换为element节点,并返回被替换的节点
void add(int index, E element)  将元素element添加到双端队列的index位置上
E remove(int index)  将此双端队列的index位置上的元素删除
    查询操作 int indexOf(Object o)  查询元素o在此双端队列中的位置(如果不存在则返回-1)
lastIndexOf(Object o)  查询元素o在此双端队列中最后一次出现的位置(如果不存在则返回-1)
boolean contains(Object o)  查询此双端队列中是否有元素o
int size()  返回此双端队列的元素数
     队列操作 E peek()  获取,但不移除此双端队列所表示的队列的头部;如果此双端队列为空,则返回 null
E element()   获取,但不移除此双端队列所表示的队列的头部
E poll()   获取并移除此双端队列所表示的队列的头部;如果此双端队列为空,则返回 null
E remove()   获取并移除此双端队列所表示的队列的头部
boolean offer(E e)   

将指定元素插入此双端队列所表示的队列,如果成功,则返回 true,如果当前没有可用的空间,则返回 false

     双端队列操作 boolean offerFirst(E e)   将指定的元素插入此双端队列的开头
boolean offerLast(E e)   将指定的元素插入此双端队列的末尾
E peekFirst()   获取,但不移除此双端队列的第一个元素;如果此双端队列为空,则返回 null
E peekLast()   获取,但不移除此双端队列的最后一个元素;如果此双端队列为空,则返回 null
E pollFirst()   获取并移除此双端队列的第一个元素;如果此双端队列为空,则返回 null
E pollLast()   获取并移除此双端队列的最后一个元素;如果此双端队列为空,则返回 null
void push(E e)  

将一个元素推入此双端队列所表示的堆栈;如果成功,则返回 true,如果当前没有可用空间,则抛出 IllegalStateException

E pop()  从此双端队列所表示的堆栈中弹出一个元素
boolean removeFirstOccurrence(Object o)  从此双端队列移除第一次出现的指定元素
boolean removeLastOccurrence(Object o)  从此双端队列移除最后一次出现的指定元素
Iterator操作 ListIterator<E> listIterator(int index) 返回此双端队列的ListIterator对象 
Iterator<E> descendingIterator()  返回以逆向顺序在此双端队列的元素上进行迭代的迭代器
数组和克隆操作 Object clone()  返回一个此双端队列的浅复制
Object[] toArray()  把此双端队列中的元素以数组的形式返回
T[] toArray(T[] a) 把此双端队列中的元素以数组的形式返回 

 

--------------------------------------------------------------------

java.util.LinkedList<E>系列文章                                            

java.util.LinkedList<E>(1)  java.util.LinkedList<E>(2)  java.util.LinkedList<E>(3)

java.util.LinkedList<E>(4)  java.util.LinkedList<E>(5)  java.util.LinkedList<E>(6)

java.util.LinkedList<E>(7)  java.util.LinkedList<E>(8)  

--------------------------------------------------------------------

相关知识                                                                             

java.util.Collection<E>   java.util.AbstractCollection<E>   java.util.List<E>

java.util.AbstractList<E>   java.util.Iterator<E>   java.util.ListIterator<E>

Java中的标记接口   迭代器模式   Java中的深拷贝和浅拷贝  java.util.Arrays

java.util.Queue<E>  java.util.Deque<E>