定义：数据结构是对在计算机内存中的数据的一种安排，也可以理解为对计算机机运算的数据单元的一个抽象。

1.集合结构 2.线性结构 3.树形结构 4.图形结构 线性机构分为：

1，顺序存储结构。2，链式存储结构List就是顺序存储结构

•优点：    尾插效率高，支持随机访问。 •缺点：    中间插入或者删除效率低。 •应用：    ArrayList2.

链式存储分为：单链，跟双链，Message消息队列

3.双链，Linkedlist代码：手写

public class LinkedList {

Node first;

Node last;

int size;

public LinkedList() {

}

public void add (E e) {

linkLast(e);

}

public void add (int index, E e) {

if(index size) {

     return;

     }

if (index == size) {

linkLast(e);

} else {

Node target = node(index);

Node pre = target.prev;

Node newNode = new Node(pre, e, target);

//有坑

// pre.next = newNode;

// pre = newNode;

if(pre == null) {

first = newNode;

} else {

pre.next = newNode;

}

pre = newNode;

size++;

}

}

    public E get(int index) {

     if(index size) {

     return null;

     }

     return node(index).item;

    }

    public void remove(int index){

     Node target = node(index);

     unlinkNode(target);

    }

    private void unlinkNode(Node p) {

     //有坑

//     p.prev.next = p.next;

//     p.next.prev = p.prev;

     Node pre = p.prev;

     Node next = p.next;

     //等价与删除第一个节点

     if (pre == null) {

first = p.next;

} else {

pre.next = p.next;

}

     //等价与删除尾节点

     if (next == null) {

last = p.prev;

} else {

next.prev = p.prev;

}

     size--;

    }

    private Node node(int index) {

     //index 处于前半部分

     if (index >1)) {

     Node node = first;

         for(int i = 0; i

         node = node.next;

         }

         return node;

} else { //index 处于后半部分

Node node = last;

for(int i = size - 1; i > index; i--) {

node = node.prev;

}

return node;

}

    }

private void linkLast(E e) {

Node newNode = new Node(last, e, null);

Node l = last;

last = newNode;

if (l == null) {

first = newNode;

}else {

l.next = newNode;

}

size ++;

}

private static class Node {

        E item;

        Node next;

        Node prev;

        Node(Node prev, E element, Node next) {

            this.item = element;

            this.next = next;

            this.prev = prev;

        }

    }

}

原文链接：http://www.apkbus.com/blog-340477-76468.html