- 浏览: 194713 次
- 性别:
- 来自: 南京
-
文章分类
最新评论
-
hahalzb：
请问文件解压缩的密码是什么呀
JMS简介与ActiveMQ实战 -
ershimengx：
JMS&ActiveMQ实战(JMS+ActiveMQ ...
JMS简介与ActiveMQ实战 -
lgh1992314：
zenghuiss 写道我书读的少，你不要蒙我哦。。。over ...
Java method invoke的指令简介 -
P00116：
...
JMS简介与ActiveMQ实战 -
风会停息丶：
你好，下载完成后解压密码是多少，跟网盘下载密码一样吗
JMS简介与ActiveMQ实战
上篇文章浅析了ArrayList的源码相关内容！这篇文章将介绍LinkedList相关的内容！
二. LinkedList
先来看看LinkedList的类结构！
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
1. 几个重要的成员变量
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;//LinkedList的长度 ，初始化为0
这里先来说一下header这个变量，这个很重要哦!
首先看一下Entry是个什么东西！
private static class Entry<E>
{
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous)
{
this.element = element;
this.next = next;
this.previous = previous;
}
}
对的，Entry就是LinkedList的一个内部静态类！我们知道LinkedList的内部数据结构采用的链式存储方式，链式存储决定了它插入的速度会相对会快，而索引的速度慢！链式存储最主要的有三个元素：当前元素、前一个元素地址、后一个元素地址。
Entry类中element表示当前元素; next表示后一个元素;previous表示前一个元素;这样的话一个链式的存储的模型就有了。
2. 两个构造函数
/**
* Constructs an empty list.
*/
public LinkedList()
{
header.next = header.previous = header;
}
无参构造函数初始化的时候header的前一个、后一个均指向本身。
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c)
{
this();
addAll(c);
}
根据已有的Collection初始化LinkedList，我们来看一个addAll(int index, Collection<? extends E> c)这个方法（addAll(Collection<? extends E> c)本身也是调用的此方法，其中index的参数值为size而已）。
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c)
{
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
modCount++;
Entry<E> successor = (index == size ? header : entry(index));
Entry<E> predecessor = successor.previous;
for (int i = 0; i < numNew; i++)
{
Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
predecessor.next = e;
predecessor = e;
}
successor.previous = predecessor;
size += numNew;
return true;
}
前面的我就不说了，都是一些预判断。我们来分析下下面这段代码的含义
Entry<E> successor = (index == size ? header : entry(index)); Entry<E> predecessor = successor.previous;
粗略的看一个successor和predecessor 英文含义分别表示为后继者和前辈;对呀，我们想啊，LinkedList本身是一个链式存储结构，你要将一些内容插入进来，首先必须要在链上找到一个入口，然后将此入口掐断，接着将你插入进来的内容放进去，最后再将这个链给接起来，你要将链给接起来要接对啊，不能接错地方啊！successor、predecessor就是为了将链接对所用，分别指向链断裂后，后一段和前一段的链接地址。
我们来看下面这两张图：
图一
图二
上面我描述的过程就类似于从图一到图二的过程。
初步感性的分析玩之后我们来详细分析一下！
这里做了一个判断：如果当前插入的index的值等于size则返回header，否则返回entry(index);
1. index == size时，其实就是插入到链尾处，因为链尾处的元素的next比较特殊，它指向了链首header。
2. index != size时，我们先来看一下entry(int index)这个方法的源码：
/**
* Returns the indexed entry.
*/
private Entry<E> entry(int index)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
Entry<E> e = header;
if (index < (size >> 1))
{
for (int i = 0; i <= index; i++)
e = e.next;
}
else
{
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
其实就是找到找到索引值为index的Entry,判断index值大小是否已经超过了size值的一半，如果没超过就从链表头部开始遍历，否则从链表尾部开始遍历。
ps:看得出来，按索引找个Entry这么麻烦，真慢，不像ArrayList来得那么直接。这就是为什么LinkedList索引慢的原因，存储结构决定的，基因问题，呵呵。
3. Entry<E> predecessor = successor.previous; 鉴于上面的分析，这句也就不难理解了。
4.
for (int i = 0; i < numNew; i++)
{
Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
predecessor.next = e;
predecessor = e;
}
这段代码就是将初始化的Collection数据一个一个链接上去。
successor.previous = predecessor; size += numNew;
最后将这个链给接回去，形成了一个闭环链！ LinkedList的大小也要增加一下嘛！
3. 几个常用方法浅析
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element)
{
addBefore(element, (index == size ? header : entry(index)));
}
有些代码是不是很熟悉啊？呵呵，还是看内部的addBefore(E e, Entry<E> entry)方法吧。
private Entry<E> addBefore(E e, Entry<E> entry)
{
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
这个还用我说吗？ 是不是比在构造方法里面的要简单得多啊。
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index)
{
return entry(index).element;
}
获取指定索引值index的元素，呵呵，不解释了！
/**
* Returns the first element in this list.
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst()
{
if (size == 0)
throw new NoSuchElementException();
return header.next.element;
}
/**
* Returns the last element in this list.
*
* @return the last element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getLast()
{
if (size == 0)
throw new NoSuchElementException();
return header.previous.element;
}
分别为获取第一个和最后一个元素的值，也很简单啊，第一个元素就是header的next的element的值，最后一个元素就是header的previous的element的值。
ps：真实的内部情况是这样的，整个链表的内容是包含header的Entry和LinkedList存储的所有Entry两个部分共同组成的。
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int indexOf(Object o)
{
int index = 0;
if (o == null)
{
for (Entry e = header.next; e != header; e = e.next)
{
if (e.element == null)
return index;
index++;
}
}
else
{
for (Entry e = header.next; e != header; e = e.next)
{
if (o.equals(e.element))
return index;
index++;
}
}
return -1;
}
返回第一个包含对象o的索引值。也很简单吧，对吧！
private E remove(Entry<E> e)
{
if (e == header)
throw new NoSuchElementException();
E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}
这是一个private方法，就是删除链表中的一个Entry，思路如下：将要移除的对象e的previous的next指向e的next,对象e的next的previous指向e的previous，就是将链表的一个节点删掉，在将这个链表接起来。
/**
* Replaces the element at the specified position in this list with the
* specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element)
{
Entry<E> e = entry(index);
E oldVal = e.element;
e.element = element;
return oldVal;
}
这个更简单，就是替换索引index的Entry的element的值。
好吧，基本常用的方法也都分析完了，重点已经照顾到了，其他的就不再累述了。
这里就简单描述一下Vector吧！
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Vector用得并不多，它和ArrayList很相似，但是它本身是线程安全的，看源码就能够看得出来，很多方法都是synchronized，但是在jdk1.6上就已经有java.util.concurrent了，对于多线程编程的话，Vector的用武之地也很少了，这里就不再讲了！
ps:附件中我上传了一个比较不错的Data Structure Visualzation工具，是一个jar包运行java -jar 执行。对于分析与理解数据结构方面的问题相当有帮助。
顶
踩
发表评论
-
Java class file format
2011-08-29 17:26 0A class file consists of a s ... -
自己动手写写：HashSet、LinkedHashSet源码浅析
2011-08-12 14:40 1930这篇文章我只是作为一个简要的分析。 首先可以看看之前写 ... -
自己动手写写：LinkedHashMap源码浅析
2011-08-11 10:31 4172此系列文章中，上一篇是关于HashMap的源码剖析，这篇文章将 ... -
自己动手写写：HashMap源码浅析
2011-08-04 13:50 4454虽说论坛中有很多关于HashMap源码的分析，并且都是分析得很 ... -
自己动手写写：ArrayList源码浅析
2011-08-02 17:29 3431了解你所使用的东西，最直接有效的方式莫过于源码切入的方式！ ...
相关推荐
源码解析jdk7.0集合：LinkedList的底层实现原理.pdf
学习linkedList源码，数据结构是链表。模仿LinkedList集合自己写一个
·企业级笔试面试题目深入源码级讲解，拒绝死记硬背 4.代码量更大、案例更丰富、更贴近实战： ·Java语言基础阶段：12720行代码，Java语言高级阶段：11684行代码 ·课堂实战项目3套，课后实战项目2套 ·近百道企业...
LinkedList的部分源码解析 包括部分常用的方法: add() ,remove(),get(),set()
LinkedList源码
第三章 LinkedList源码解析一、对于LinkedList需要掌握的八点内容LinkedList的创建：即构造器往LinkedList中添加对象：即add
java软件技术文档
这是我从JDK中拿出的Arraylist，Vector，LinkedList源码，自己看源码的时候弄出来的，并写了一点自己的分析，仅供源码分析者使用
LinkedList源码分析_016.pdf
LinkedList同时实现了List接口和Deque接口，也是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。这样看来，LinkedList简直是个全能。当你需要使用栈或者队列时，可以...
LinkedList_example LinkedList Javascript
linkedList 使用C语言在LinkedlIst上的操作
LinkedList源码分析，java作业，主要是对rar包中的LinkedList分析
链表 LinkedList上的程序
列表ADT LinkedList，Doubly LinkedList和ArrayList的Python实现
leetcode 2 和 c 我的 LeetCode 方式 # 问题名称 ...LinkedList 206 Easy :snail: LinkedList 234 Easy :fire: :thumbs_up: LinkedList 237 Easy :snail: LinkedList 876 Easy :flushed_face: LinkedList |
资源分类：Python库 所属语言：Python 资源全名：linkedlist-1.0.1.tar.gz 资源来源：官方 安装方法：https://lanzao.blog.csdn.net/article/details/101784059
单双链表的创建，节点的添加与删除，链表逆序，链表遍历。
ArrayList-LinkedList-源码.rar
简介：写一个链表的数据结构，要求实现IList接口。 具体要求： 1、 使用代码规范。 2、 至少对IList中的Add，Remove，Insert，Indexer，IEnumerator进行单元测试。 3、 对上述每个单元测试方法至少书写4种不同的单元...