\(2.3\)双链表

1.对addLast的优化

  让我们回顾一下\(SLList\)的addList方法：

public void addLast(int x) {
    size += 1;
    IntNode p = sentinel;
    while (p.next != null) {
        p = p.next;
    }

    p.next = new IntNode(x, null);
}

  这个方法的问题在于速度太慢。对此，我们可以像处理\(size\)一样，在链表中多存储一个关键信息\(last\)：

public class SLList {
    private IntNode sentinel;
    private IntNode last;
    private int size;

    public void addLast(int x) {
        last.next = new IntNode(x, null);
        last = last.next;
        size += 1;
    }
    ...
}

  但这样会让deleteLast的操作变得困难，因为要删除\(last\)，必须知道\(last\)前面的元素。如果我们再缓存\(secondlast\)，就相应地需要缓存\(thirdlast\)...这说明缓存并不能解决问题，这引出了我们下面的解决方案：

2.指向前面元素的指针

  上面问题的解决方案就是给\(IntNode\)添加一个指向前面元素的指针：

public class IntNode {
    public IntNode prev;
    public int item;
    public IntNode next;
}

  通过这种操作，我们的链表就与前后两个节点都产生了链接。这种链表被称为双链表(\(double\;linked\;list\))。下面的图示显示了双链表的具体构建：

3.哨兵节点的改进

  向后的指针有时会指向哨兵节点，有时会指向真实节点，在特殊情况下，这会导致原先代码的错误。对此，我们有两种解决办法：

1. 在前后各设置一个哨兵节点：

2. 将链表变为循环链表：

4.通用型链表

  有时，链表中的元素不止是\(int\)型，还可能是其他类型。我们可以用以下语句声明能表示任何引用类型的数据结构：

/*create a class able to contain any type*/
public class DLList<T> () {
    //create an item able to carry any type
    public T item;
    //create an array able to carry any type
    public T[] arr = (T[])new Object[capacity]; 
    //print this type of item
    System.out.println(item);
}