DLList

我们现在需要一个双向链表，如何实现呢？

从SLList来说，我们创建了一个哨兵节点，那最直观的想法是：在尾部也创建一个节点。

但是存在另一种可能性：直接让这个哨兵节点的prev指向尾部，形成了一个环的结构，从而方便的构建一个双向链表

class DLList<T>{
    //Node
    class Node{
        public T? item;
        public Node? next;
        public Node? prev;
        public Node(T? value, Node? next,Node? prev)
        {
            this.item = value;
            this.next = next;
            this.prev = prev;
        }
    }

    //DLList    

    private Node sentinel;
    public int size = 0;

    public DLList(){
        sentinel = new Node(default,sentinel,sentinel);
    }

    public DLList(T item){
        sentinel = new Node(default,null,null);
        sentinel.next = new Node(item,null,null);
        sentinel.prev = sentinel.next;
        size += 1;
    }

    public void AddFirst(T item){
        sentinel.next = new Node(item,sentinel.next,sentinel);
        size += 1;
    }

    public void AddLast(T item){
        sentinel.prev = new Node(item,sentinel.prev,sentinel);
        size += 1;
    }

    public void RemoveLast(){
        sentinel.prev.prev.next = sentinel;
        sentinel.prev = sentinel.prev.prev;
    }

    public int GetSize(){
        return size;
    }

    //public T  GetItem(int index)
    //{
    //不想写了
    //}
}