数据结构学习笔记：链表原理及其实现

链表是一种物理存储单元上非连续、非顺序的存储结构，并且是一种动态的数据结构。链表由节点（Node）构成。
链表的各个节点在内存上是随机分布的，因而不能轻易的像数组那样通过索引获得数据，但是对于存储无语义型的数据（如手机号码，身份证号等），我们优先使用链表，这样无需开辟过多的内存空间。
一个节点由一个Node型的next和一个存储数据的泛型变量e组成。next指的是下一个节点所在的位置，而e就是存储的实际数据了。整个链表通过一个个节点通过next链接起来，最后一个节点的下一个值则为 NULL 。我们将链表的头所在位置用head变量标记。

链表简图
下面我们使用 Java 来实现链表。

public class LinkedList<E> {
    private Node head;
    private int size;

    public LinkedList(){
        head=null;
        size=0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    public void add(int index,E e){//模拟数组添加数据到指定索引节点
        if (index <0 ||index > size)
            throw new IllegalArgumentException("ADD FAILED.");
        if (index==0){
            head=new Node(e,head.next);
            size++;
        }else{
            Node prev=head;
            for (int i=0;i<index-1;i++){
                prev=prev.next;
            }
            prev.next=new Node(e,prev.next);
            size++;
        }
    }

    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();
        }
    }
}

由于每次添加操作还要对index==head的情况额外进行判断，我们引入dummyHead（虚拟头结点）。
所谓虚拟头节点，就是在head之前添加一个虚拟的头节点，这样子就无需进行额外判断。

重新编写的代码如下：

增

    public void add(int index,E e){
        if (index <0 ||index > size)
            throw new IllegalArgumentException("ADD FAILED.");
            Node prev=dummyHead;
            for (int i=0;i<index;i++){//由于是从head前一个节点开始遍历，我们只需遍历index次
                prev=prev.next;
            }
            prev.next=new Node(e,prev.next);
            size++;
    }

删

    public E remove(int index){
        if (index <0 || index >= size)
            throw new IllegalArgumentException("REMOVE FAILED.");
        Node cur = dummyHead.next;
        for (int i=0;i<index;i++){
            cur = cur.next;
        }
        Node ret=cur.next;
        cur.next=ret.next //cur.next=cur.next.next;
        ret.next=null;
        size--;
        return ret.e;
    }

改

    public void set(int index,E e){
        if (index <0 || index >= size)
            throw new IllegalArgumentException("SET FAILED.");
        Node cur = dummyHead.next;
        for (int i=0;i<index;i++){
            cur = cur.next;
        }
        cur.e= e;
    }

查

    public E get(int index){
        if (index <0 || index >= size)
            throw new IllegalArgumentException("GET FAILED.");
        Node cur = dummyHead.next;
        for (int i=0;i<index;i++){
            cur = cur.next;
        }
        return cur.e
    }

    public boolean contains(E e){
        Node cur = dummyHead.next;
        while(cur != null){
            if (cur.e.equals(e))
                return true;
            cur=cur.next;
        }
        return false;
    }