实现一个功能齐全的链表

首先说明什么是链表，直接给张图

image.png

看的懂吧，看懂我们就开始写了。
等下，我们为什么要写链表，也就是为什么要有这种数据结构，它的功能是什么？
很简单啦，因为数组的插入和删除太耗时间了，我们需要个数据结构解决这个问题。什么？你问我为什么数组的插入和删除耗时间？emmm，自己想想吧。。。

先在eclispe中新建一个class（废话），我们命名为MyprototypeLinkedList，
prototype意思是原型，模板，我写的这个链表功能上参照jdk源码中的LinkedList，功能上来说应该是比较齐全的了，就取个这个名字。
开始写代码..

停！闷头写代码是程序员最忌讳的东西，在代码前应该认真分析需求，设计好整个流程，再来写。我们先来看LinkedList中有什么api可以调用。

image.png

这。。好像有点多，不过我们能看到主要的一些api，增删改查嘛，add，set，remove，update，再来几个常用的clear，size，isEmpty，行了，差不多可以了。我们的链表就做这些api的需求。

明确了需求，接下来写就完事了。
首先给类明确几个属性，Node head，Node end，int size；
这是什么？首先我需要确定链表的头尾，所以在属性上就先声明了。size是链表目前存储值得数量。
等一下，Node是什么？
Node顾名思义，就是节点啦，还没写呢，我们用个私有静态内部类来解决
，Node存储得数据我希望不定死，所以使用泛型T，Node中得属性分别为
public T data，（结点中得数据），public Node<T> next;(指向后置结点)
public Node<T> prev；（指向前置结点）
ps：当然用双向链表啦，单向的太难用了，不适合。
现在 我们的代码大概是这个亚子

package 链表;
public class MyprototypeLinkedList<T> {
    private Node<T> head;
    private Node<T> end;
    private int size;
    private static class Node<T>{
        public T data;
        public Node<T> next;
        public Node<T> prev;
        public Node() {
            this(null,null,null);
        }
        public Node(T data, Node<T> next, Node<T> prev) {
            super();
            this.data = data;
            this.next = next;
            this.prev = prev;
        }       
    }
}

如果你现在把我的程序复制上去，eclipse上会报好多警告，（强迫症福利），其实是因为我们的属性以及Node，都设成private的了，eclipse看到我们写了这么多私有，却都没调用，就认为是废代码，提醒我们删除。
行吧，接下来我们就用起来吧。

首先是类构造方法吧，要初始化3个属性。本来准备这样写

public MyprototypeLinkedList() {
    }
    public MyprototypeLinkedList(Node<T> head, Node<T> end, int size) {
        super();
        this.head = head;
        this.end = end;
        this.size = size;
    }

但是啊，初始化类属性完全可以抽出来嘛，因为clear方法也是相当于重新执行一遍以上的构造。那么我们可以这样写：

public MyprototypeLinkedList() {
             doClear();
    }
    public void clear() {
             doClear();
    }

    private void doClear() {
        head=new Node<T>();
        end=new Node<T>(null,null,head);
        head.next=end;
        size++;
    }

是不是看起来好多了。一个私有的doClear方法，解决了初始化属性和clear功能，这就是代码的复用，或者说封装。
经过初始化，现在结点的关系大概是这样的

image.png

ok，接下来要干啥，当然是增删改查了。先写最复杂的增，首先增应该给两种方法，一种默认的add（T x），直接将新结点加在链表的尾部。一种重载的add（int idx,T x），指定在链表的哪个位置增加结点。那么其实所谓的默认add就是add（size，T x），所以我们可以这样写，顺变把size方法也给写了。

public void add(T x) {
        add(size(),x);
    }
public void add(int idx,T x) {
        
    }
public int size() {
        return size;
    }

接下来就是怎么完成这个add方法了，我们知道，要想在链表中添加结点，那么我们需要在要添加的位置将前置结点的next指向新结点，新节点的prev指向前置结点，后置结点的prev指向新结点，新结点的next指向后置结点。

image.png

我们想在idx这个索引位置添加新结点，那么首先就要找到这个现在在idx位置的结点当作aim，然后新结点的prev连接aim的前置结点，新结点的next在连接aim。
明确了目标，那就写吧，首先我要一个方法能找到目前在idx位置的结点。

等等！我们要知道，程序员是很蠢的，他很可能给的idx是一个负数，还有可能给出一个大于size的数。要是这样那我写的链表不就废了？我得搞个异常提醒下他。
还有，既然是双向链表，那么我们可以优化下查询嘛，如果idx在前半部分，我们从head往后查，如果idx在后半部分，我们从end往前查。
终于，我们开始写了。

得到在idx索引的结点

private Node<T> getNode(int lower,int idx,int upper){
        Node<T> p;
        if(idx<lower||idx>upper) {
            throw new IndexOutOfBoundsException();
        }
        if(idx<size()/2) {
            p=head.next;
            for(int i=0;i<idx;i++) {
                p=p.next;
            }
        }
        else {
            p=end.prev;
            for(int i=size();i>idx;i--) {
                p=p.prev;
            }
        }
        return p;
    }

大功告成，我们在来写一个addBefore方法，来实现在idx索引下结点前的结点插入。它需要的参数很显然了，就是我们的aim结点，和T x

private void addBefore(Node<T> node, T x) {
        Node<T> newNode=new Node<T>(x,node,node.prev);
        node.prev.next=newNode;
        node.prev=newNode;
                size++;
    }

最后我们让我们的add方法调用下addBefore即可。

public void add(int idx,T x) {
        addBefore(getNode(0,idx,size()),x);
    }

完成！！

四分之一。我们还要写删改查啊。接着干。
接下来写查。我们知道，查，只要找到那个结点，直接Node.data不就完事了嘛，我们还知道，我们刚刚就写过一个根据索引找到结点的方法！
问题是不是很简单了

public T get(int idx) {
        return getNode(idx).data;
    }   
    private Node<T> getNode(int idx){
        return getNode(0, idx, size());
    }

过瘾吧，接下来写删。我们知道，删的话，同样要定位到目标结点，是不是我们又写过了！
等下，除了定位，我们还要做的是，把它的前置结点和后置结点连起来即可，至于要删的，谁管它，java垃圾回收比c++好用。当然为了告诉程序员真的删掉了，我们将删除结点的data域取出来，给调用的程序员留个纪念。

image.png

public T remove(int idx) {
        return remove(getNode(idx));
    }
    private T remove(Node<T> node) {
        node.prev.next=node.next;
        node.next.prev=node.prev;
        size--;
        return node.data;
    }

最后写个改，update嘛，我们能找到索引的aim结点（不想强调了，所以说封装很重要啊），改下data域即可。当然为了告诉笨笨的程序员真的改掉了，我们将被改掉的data送给他。
直接上代码吧。

public T update(int idx,T x) {
        return update(getNode(idx),x);
    }
    private T update(Node<T> node,T x) {
        T old=node.data;
        node.data=x;
        return old;
    }

写完了，好像少了一个isEmpty，给出来吧

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

最后给整体代码吧

package 链表;
public class MyprototypeLinkedList<T> {
    private Node<T> head;
    private Node<T> end;
    private int size;
    private static class Node<T>{
        public T data;
        public Node<T> next;
        public Node<T> prev;
        public Node() {
            this(null,null,null);
        }
        public Node(T data, Node<T> next, Node<T> prev) {
            super();
            this.data = data;
            this.next = next;
            this.prev = prev;
        }       
    }
    
    public MyprototypeLinkedList() {
             doClear();
    }
    public void clear() {
             doClear();
    }

    private void doClear() {
        head=new Node<T>();
        end=new Node<T>(null,null,head);
        head.next=end;
        size++;
    }
    public int size() {
        return size;
    }
    public boolean isEmpty() {
        return size()==0;
    }
    public void add(T x) {
        add(size(),x);
    }
    public void add(int idx,T x) {
        addBefore(getNode(0,idx,size()),x);
    }
    public T get(int idx) {
        return getNode(idx).data;
    }
    public T remove(int idx) {
        return remove(getNode(idx));
    }
    public T update(int idx,T x) {
        return update(getNode(idx),x);
    }
    private T update(Node<T> node,T x) {
        T old=node.data;
        node.data=x;
        return old;
    }
    private T remove(Node<T> node) {
        node.prev.next=node.next;
        node.next.prev=node.prev;
        size--;
        return node.data;
    }
    
    private Node<T> getNode(int idx){
        return getNode(0, idx, size());
    }
    private Node<T> getNode(int lower,int idx,int upper){
        Node<T> p;
        if(idx<lower||idx>upper) {
            throw new IndexOutOfBoundsException();
        }
        if(idx<size()/2) {
            p=head.next;
            for(int i=0;i<idx;i++) {
                p=p.next;
            }
        }
        else {
            p=end.prev;
            for(int i=size();i>idx;i--) {
                p=p.prev;
            }
        }
        return p;
    }
    private void addBefore(Node<T> node, T x) {
        Node<T> newNode=new Node<T>(x,node,node.prev);
        node.prev.next=newNode;
        node.prev=newNode;
        size++;
    }
}

image.png