作者：whisper

链接：http://proprogrammar.com:443/article/248

声明：请尊重原作者的劳动，如需转载请注明出处

    完成前面的章节后，你至少应该熟悉了单链表。

    本章节中，我们将介绍另一种链表：双链表。与单链表不同的是，双链表的每个结点中都含有两个引用字段。

    我们将在本章中介绍更多详细信息，并帮助你了解双链表中的基本操作。

    简介 - 双链表

    我们在前面的章节中介绍了单链表。

单链接列表中的结点具有 Value 字段，以及用于顺序链接结点的“Next”引用字段。

    在本文中，我们将介绍另一种类型的链表：双链表。

    定义

    双链表以类似的方式工作，但还有一个引用字段，称为“prev”字段。有了这个额外的字段，您就能够知道当前结点的前一个结点。

    让我们看一个例子：

    绿色箭头表示我们的“prev”字段是如何工作的。

    结点结构

    下面是双链表中结点结构的典型定义：

// Definition for doubly-linked list.
class DoublyListNode {
    int val;
    DoublyListNode next, prev;
    DoublyListNode(int x) {val = x;}
}

    与单链接列表类似，我们将使用头结点来表示整个列表。

    操作

    与单链表类似，我们将介绍在双链表中如何访问数据、插入新结点或删除现有结点。

    我们可以与单链表相同的方式访问数据：

1. 我们不能在常量级的时间内访问随机位置。
2. 我们必须从头部遍历才能得到我们想要的第一个结点。
3. 在最坏的情况下，时间复杂度将是 O(N)，其中 N 是链表的长度。

    对于添加和删除，会稍微复杂一些，因为我们还需要处理“prev”字段。在接下来的两篇文章中，我们将介绍这两个操作

    之后，我们提供练习，让你使用双链表重新设计链表。

    添加操作 - 双链表

    如果我们想在现有的结点 prev 之后插入一个新的结点 cur，我们可以将此过程分为两个步骤：

1. 链接 cur 与 prev 和 next，其中 next 是 prev 原始的下一个节点；
2. 用 cur 重新链接 prev 和 next。

    与单链表类似，添加操作的时间和空间复杂度都是 O(1)。

    示例

    让我们在现有结点 6 之后添加一个新结点 9：

1. 链接 cur（结点 9）与 prev（结点 6）和 next（结点 15）
2. 用 cur（结点 9）重新链接 prev（结点 6）和 next（结点 15）

如果我们想在开头或结尾插入一个新结点怎么办？ 

    删除操作 - 双链表

    如果我们想从双链表中删除一个现有的结点 cur，我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。

与单链表不同，使用“prev”字段可以很容易地在常量时间内获得前一个结点。

    因为我们不再需要遍历链表来获取前一个结点，所以时间和空间复杂度都是O(1)。

    示例

    我们的目标是从双链表中删除结点 6。

    因此，我们将它的前一个结点 23 和下一个结点 15 链接起来：

    结点 6 现在不在我们的双链表中。

如果我们要删除第一个结点或最后一个结点怎么办？

    算法说明

     设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

提示：

• 所有val值都在 [1, 1000] 之内。
• 操作次数将在  [1, 1000] 之内。
• 请不要使用内置的 LinkedList 库。

class MyLinkedList {
    ListNode head;
    int len;
    
    /** Initialize your data structure here. */
    public MyLinkedList() {
        len = 0;
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if(index >= len || index < 0){
            return -1;
        }
        
        ListNode temp = head;
        for(int i = 1; i <= index; i++){
            temp = temp.next;
        }
        
        return temp.val;
    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        ListNode temp = new ListNode(val);
        
        if(head == null){
            head = temp;
        }else{
            temp.next = head;
            head = temp;
        }
        
        len++;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        if(null == head){
            head = new ListNode(val);
        }else{
            ListNode temp = head;
            for(int i = 1; i < len; i++){
                temp = temp.next;
            }
            
            temp.next = new ListNode(val);
        }
        
        len++;
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        if(index <= 0){
            addAtHead(val);
        }else if(index < len){
            ListNode temp = head;
            
            for(int i = 1; i < index; i++){
                temp = temp.next;
            }
            
            ListNode newNode = new ListNode(val);
            newNode.next = temp.next;
            temp.next = newNode;
            
            len++;
            
        }else if(index == len){
            addAtTail(val);
        }
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if(index < len && index >= 0){
            ListNode temp = head;
            
            if(index == 0) {
            	head = head.next;
            }else {
	            for(int i = 1; i < index; i++){
	                temp = temp.next;
	            }
	            
	            temp.next = temp.next.next;
            }
            
            len--;
        }
    }
    
    private class ListNode{
        int val;
        ListNode next;
        
        public ListNode(int val){
            this.val = val;
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

     定义了链表入口变量和长度变量以方便插入，删除时的判断，看一下更好的代码

/**
 * A singly linked list with a left sentinel node.
 */
class MyLinkedList {

	/** A very simple node class. */
	private static class Node {
		int val;
		Node next;
	}

	// Predecessor of the first element
	private Node headPred;
	// Predecessor of the tail
	private Node tailPred;
	private int length;

	/** Initialize your data structure here. */
	public MyLinkedList() {
		headPred = new Node();
		tailPred = headPred;
		length = 0;
	}

	/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
	public int get(int index) {
		if ((index < 0) || (index >= length)) {
			return -1;
		}
		return findPred(index).next.val;
	}

	/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
	public void addAtHead(int val) {
		if (length == 0) {
			addAtTail(val);
		} else {
			addAfter(headPred, val);
		}
	}

	/** Append a node of value val to the last element of the linked list. */
	public void addAtTail(int val) {
		addAfter(tailPred, val);
		tailPred = tailPred.next;
	}

	/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
	public void addAtIndex(int index, int val) {
		if (index < 0) {
			addAtHead(val);
		} else if (index == length) {
			addAtTail(val);
		} else if ((index >= 0) && (index < length)) {
			addAfter(findPred(index), val);
		}
	}

	/** Delete the index-th node in the linked list, if the index is valid. */
	public void deleteAtIndex(int index) {
		if ((index >= 0) && (index < length)) {
			Node pred = findPred(index);
			if (index == length - 1) { // Remove last element
				// Move tail to the left
				tailPred = pred;
			}
			pred.next = pred.next.next;
			--length;
		}
	}

	/** Return the predecessor of the index-th node. */
	private Node findPred(int index) {
		Node pred = headPred;
		for (int i = 0; i < index; ++i) {
			pred = pred.next;
		}
		return pred;
	}

	/** Add an element after the given node. */
	private void addAfter(Node pred, int val) {
		Node node = new Node();
		node.val = val;
		node.next = pred.next;
		pred.next = node;
		++length;
	}
}

    这里不但定义了头指针（在第一个节点前）和长度，还定义了尾指针（在最后一后节点前）以方便操作尾部，还定义了两个方法findPred（找索引元素的前一个元素）和addAfter（在当前元素后插入一个元素），来进行相关的插入，删除操作，这里的技巧是利用了前一个元素来操作（插入，删除）后一个位置

亲爱的读者：有时间可以点赞评论一下