1.介绍
链表是数据结构中一种很重要的数据结构，一个链表含有一个或者多个节点，每个节点处理保存自己的信息之外还需要保存上一个节点以及下一个节点的指针信息。通过链表的表头就可以访问整个链表的信息。Java API中提供了链表的Java实现---LinkedList下。LinkedList是通过节点的连接实现链表的数据结构，向linkedList中插入或删除元素的速度是特别快，而随机访问的速度相对较慢，这个是由于链表本身的性质造成的，在链表中，每个节点都包含了前一个节点的引用，后一个节点的引用和节点存储值，当一个新节点插入式，只需要修改其中相关的前后关系节点引用即可，删除节点也是一样。操作对象只需要改变节点的链接，新节点可以存放在内存的任何位置，但也就是因为如此LinkedList虽然存在get()方法，但是这个方法通过遍历节点来定位所以速度很慢。LinkedList还需要单独addFrist(),addLast(),getFrist(),getLast(),removeFirst(),removeLast()方法，这些方法使得LinkedList可以作为堆栈，队列，和双队列来使用。下面是LinkedList使用的简单示例：
package com.test.collections; import java.util.LinkedList; public class LinkedListTest { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub LinkedList<String> linkedList = new LinkedList<String>(); linkedList.add("A"); linkedList.add("B"); linkedList.add("C"); linkedList.add("D"); linkedList.add("E"); linkedList.add("F"); linkedList.addFirst("G"); linkedList.addLast("H"); System.out.println(linkedList.element()); System.out.println(linkedList.contains("A")); System.out.println(linkedList.element()); System.out.println(linkedList.get(4)); System.out.println(linkedList.getFirst()); System.out.println(linkedList.getLast()); System.out.println(linkedList.indexOf("C")); System.out.println(linkedList.contains("D")); System.out.println(linkedList.offer("F")); System.out.println(linkedList.isEmpty()); System.out.println(linkedList.iterator().next()); linkedList.push("N") ; } } |
2.继承结构
LinkedList继承了AbstractSequentialList类，实现了List<E>, Deque<E>, Cloneable, Serializable这几个接口，含有三个transient类型的属性size,Node<E>类型的first和last;first 指向了第一个节点指针，last指向了最后一个节点的指针。还需要说明的几点是ListedList的几个内部类，实现了ListIterator接口的ListItr类，保存节点信息的Node类，实现了Iterator<E接口的DescendingIterator类，提供了向下的迭代器实现。我们重点看下Node节点做了什么事情。
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;
}
}
Node节点中item保存具体的对象的值，next节点指向下一个节点指针，prev指向了上一个节点的指针。
