完全沒想到啊，講完Linked List 的基本概念跟操作之後，馬上就接著要你自己手刻一個Linked List 出來，不能使用各個程式語言的Library，這道題目在LeetCode Problem 中是屬於Medium 的等級。

707. Design Linked List

題目

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.

A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.

If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

• MyLinkedList() Initializes the MyLinkedList object.
• int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return 1.
• void addAtHead(int 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.
• void addAtTail(int val) Append a node of value val as the last element of the linked list.
• void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If indexequals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
• void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

Example 1:

Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]

Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

Constraints:

• 0 <= index, val <= 1000
• Please do not use the built-in LinkedList library.
• At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

解法(Java)

我這個解法算是只依照前面介紹的，對鏈結陣列的操作都是先【透過遍歷的方式到達指定位置】再進行指定操作，因此執行效率上會比其他解法慢一點，我看Java 的Library 中有多設定了尾端跟數量，這在部分操作上效率會更快。

Runtime: 9 ms
Memory Usage: 44.1 MB

class MyLinkedList {
    
    private Node head;

    public MyLinkedList() {
        
    }
    
    public int get(int index) {
        int cur = 0;
        Node temp = this.head;
        while (cur != index && null != temp.getNext()) {
            temp = temp.getNext();
            cur++;
        }
        
        if (cur == index && temp != null) {
            return temp.getVal();
        }
        
        return -1;
    }
    
    public void addAtHead(int val) {
        Node node = new Node();
        node.setVal(val);
        node.setNext(head);
        
        this.head = node;
    }
    
    public void addAtTail(int val) {
        Node node = new Node();
        node.setVal(val);
        
        Node temp = this.head;
        if (temp == null) {
            this.head = node;
        } else {
            while (null != temp.getNext()) {
                temp = temp.getNext();
            }
            temp.setNext(node);
        }
    }
    
    public void addAtIndex(int index, int val) {
        Node node = new Node();
        node.setVal(val);
        
        Node temp = this.head;
        if (index == 0) {
            this.addAtHead(val);
        } else if (null != temp) {
            int cur = 0;
            while (cur != index - 1 && null != temp.getNext()) {
                temp = temp.getNext();
                cur++;
            }

            if (cur == index - 1) {
                Node next = temp.getNext();
                node.setNext(next);
                temp.setNext(node);
            }
        }
    }
    
    public void deleteAtIndex(int index) {
        if (index == 0) {
            this.head = head.getNext();
        } else {
            int cur = 0;
            Node temp = this.head;
            while (cur != index - 1 && null != temp.getNext()) {
                temp = temp.getNext();
                cur++;
            }

            if (null != temp.getNext()) {
                Node delete = temp.getNext();
                temp.setNext(delete.getNext());
            }
        }
    }
}

class Node {
    
    private int val;
    
    private Node next;
    
    public void setVal(int val) {
        this.val = val;
    }
    
    public int getVal() {
        return this.val;
    }
    
    public void setNext(Node next) {
        this.next = next;
    }
    
    public Node getNext() {
        return this.next;
    }
    
}

/**
 * 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);
 */

小結

在我目前的職涯中，還沒看過其他資深工程師使用過LinkedList，基本上都是使用ArrayList，可能是因為環境問題吧，不過這也不代表其他地方不會用到，知道它的原理跟使用情境，等到未來有機會遇到的時候才會解！