一 、概述
LinkedList与ArrayList一样实现List接口，只是ArrayList是List接口的大小可变数组的实现，LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。
LinkedList实现所有可选的列表操作，并允许所有的元素包括null。
除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
此类实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。
所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。
同时，与ArrayList一样此实现不是同步的。
二、底层实现加深理解创建一个节点类package com.gcx.demo2; public class Node { Node previous; Object obj; Node next; public Node() { // TODO Auto-generated constructor stub } public Node(Node previous, Object obj, Node next) { super(); this.previous = previous; this.obj = obj; this.next = next; } public Node getPrevious() { return previous; } public void setPrevious(Node previous) { this.previous = previous; } public Object getObj() { return obj; } public void setObj(Object obj) { this.obj = obj; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } @Override public String toString() { return "Node [previous=" + previous + ", obj=" + obj + ", next=" + next + "]"; } }
底层实现 package com.gcx.demo2; public class Demo2 { private Node first; private Node last; private int size; /** * 添加节点 * @param obj */ public void add(Object obj){ Node n=new Node(); if(first==null){ n.setPrevious(null); n.setObj(obj); n.setNext(null); first=n; last=n; }else{ n.setPrevious(last); n.setObj(obj); n.setNext(null); last.setNext(n); last=n; } size++; } /** * 返回个数大小 * @return */ public int size(){ return size; } /** * 获得指定节点 * @param index * @return */ public Object get(int index){ RangeCheck(index); Node temp=node(index); if(temp!=null){ return temp.obj; } return null; } /** * 判断是否越界 * @param index */ public void RangeCheck(int index){ if(index>=size){ try { throw new Exception(); } catch (Exception e) { e.printStackTrace(); } } } /** * 指定节点 * @param index * @return */ public Node node(int index){ Node temp=null; if(first!=null){ temp=first; for(int i=0;i<index;i++){ temp=temp.next; } } return temp; } /** * 移除节点 * @param index */ public void remove(int index){ Node temp=node(index); if(temp!=null){ Node up=temp.previous; Node down=temp.next; up.next=down; down.previous=up; } size--; } /** * 添加指定索引处的节点 * @param index * @param obj */ public void add(int index,Object obj){ Node temp=node(index); Node newNode=new Node(); newNode.obj=obj; if(temp!=null){ Node up=temp.previous; up.next=newNode; newNode.previous=up; newNode.next=temp; temp.previous=newNode; size++; } } public static void main(String[] args) { Demo2 d=new Demo2(); d.add("aa"); d.add("bb"); d.add(1,"gggg"); d.add("cc"); //d.remove(1); System.out.println(d.size()); System.out.println(d.get(1)); } }
