链表

链表有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。

链表:真正的动态数据结构

• 数据存储在“节点”(Node) 中
• 优点: 真正的动态，不需要处理固定容量的问题
• 缺点: 丧失了随机访问的能力

  class Node {
    E е;
    Node next;
  }

  

数组和链表的对比

数组

• 数组最好用于索引有语意的情况。scores[2]

• 最大的优点:支持快速查询

  链表

• 链表不适合用于索引有语意的情况

• 最大的优点:动态

添加操作

addLast(e) O(n)
addFirst(e) O(1)
add(index, e) O(n/2) = O(n)

删除操作

removeLast(e) O(n)
removeFirst(e) O(1)
remove(index, e) O(n/2)= O(n)

修改操作

set(index,e) O(n)

查找操作

get(index) O(n)
contains(e) O(n)

package com.hoho.datastruture.LinkedList;
import com.sun.xml.internal.bind.marshaller.NoEscapeHandler;
import sun.tools.tree.ForStatement;
import sun.tools.tree.NewArrayExpression;
import javax.xml.soap.Node;
/**
 * 链表
 *
 * @author tlc
 */
public class LinkedList<E> {
    private class Node {
        public E e;
        public Node next;
        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }
        public Node(E e) {
            this(e, null);
        }
        public Node() {
            this(null, null);
        }
        @Override
        public String toString() {
            return e.toString();
        }
    }
    //虚拟头结点
    private Node dummyHead;
    private int size;
    public LinkedList() {
        dummyHead = new Node(null, null);
        size = 0;
    }
    public int getSize() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    //在链表头添加
    public void addFirst(E e) {
        add(0, e);
    }
    //在链表中间 添加
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add Failed. Require index > 0 & index <= size");
        }
        //先要找到待插入节点的前一个节点
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        //插入新的节点
        prev.next = new Node(e, prev.next);
        size++;
    }
    public void addLast(E e) {
        add(size, e);
    }
    public E get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("get Failed. Require index > 0 & index <= size");
        }
        //链表的实际第一个节点
        Node current = dummyHead.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.e;
    }
    public E getFirst() {
        return get(0);
    }
    public E getLast() {
        return get(size - 1);
    }
    public void setDummyHead(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Set Failed. Require index > 0 & index <= size");
        }
        Node current = dummyHead.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        current.e = e;
    }
    public boolean contains(E e) {
        Node current = dummyHead.next;
        while (current != null) {
            if (current.e.equals(e)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }
    public E remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Set Failed. Require index > 0 & index <= size");
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size--;
        return retNode.e;
    }
    public E removeFirst(){
        return remove(0);
    }
    public E removeLast(){
        return remove(size-1);
    }
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        Node current = dummyHead.next;
        while (current != null) {
            res.append(current + " -> ");
            current = current.next;
        }
        res.append("NULL");
        return res.toString();
    }
}