从0构建一个链表

IntList

使用链表，构建一个列表：

    class Node{
    public int item;
    public Node? next;

    public Node(int value, Node? next = null){
        this.item = value;
        this.next = next;
      }
    }

SLList

显然，直接在列表里添加函数方法太过于简陋，且无法实现不需要遍历列表即可获取列表长度的方法，于是我们使用新的类将其封装

原始SLList

public class SLList {
    public Node first;

    public SLList(int x) {
        first = new Node(x, null);
    }

    /** Adds an item to the front of the list. */
    public void addFirst(int x) {
        first = new Node(x, first);
    }
}

但是这样做存在两个问题：

• first节点对外裸露

• 若创建空列表,由于first节点为null，无法正确addLast

为了解决上面两个问题，可以把public改为private，并创建一个哨兵节点（虚拟头节点），我们令这个哨兵节点始终位于最前端且被实例化，可以规避由于null导致无法addLast的问题

修改后的SLList

class SLList{
    //Node
    class Node{
    public int item;
    public Node? next;

    public Node(int value, Node? next = null){
        this.item = value;
        this.next = next;
      }
    }

    //SLList    

    private Node sentinel;
    public int size = 0;

    public SLList(){
        sentinel = new Node(0,null);
    }

    public SLList(int item){
        sentinel = new Node(0,null);
        sentinel.next = new Node(item,null);
        size += 1;
    }

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

    public void AddLast(int item){
        Node p = sentinel;
        while(p.next != null){
            p = p.next;
        }
        p.next = new Node(item,null);
        size += 1;
    }

    public int GetSize(){
        return size;
    }

    public int GetItem(int index)
    {
        Node p = sentinel;
        while(index >= 0 && p.next != null){
            p = p.next;
            index--;
        }
        return p.item;
    }
}

修改后的SLList也有需要优化的地方：

• 现在这个SLList是单向的，也就是说不管访问哪个节点都会从头开始遍历，当我们想要访问或添加/删除靠后的节点时，每次访问都需要先经过不必要的遍历，不是吗？