[TOC] ## Solution --- #### Interview Strategy [Linked List](https://en.wikipedia.org/wiki/Linked_list#Basic_concepts_and_nomenclature) is a data structure with zero or several elements. Each element contains a value and link(s) to the other element(s). Depending on the number of links, that could be singly linked list, doubly linked list and multiply linked list. Singly linked list is the simplest one, it provides `addAtHead` in a constant time, and `addAtTail` in a linear time. Though doubly linked list is the most used one, because it provides both `addAtHead` and `addAtTail` in a constant time, and optimises the insert and delete operations. Doubly linked list is implemented in Java as [LinkedList](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html). Since these structures are quite well-known, a good interview strategy would be to mention them during the discussion but not to base the code on them. Better to use the limited interview time to work with two ideas: - [Sentinel nodes](https://leetcode.com/articles/remove-linked-list-elements/) >Sentinel nodes are widely used in the trees and linked lists as _pseudo-heads_, _pseudo-tails_, _etc_. They serve as the guardians, as the name suggests, and usually they do not hold any data. Sentinels nodes will be used here to simplify insert and delete. We would apply this in both of the following approaches. - Bidirectional search for doubly-linked list Rather than starting from the head, we could search the node in a doubly-linked list from both head and tail. If you are familiar with the concepts, you can start directly from the Approach #2. By the way, the Approach #2 is 90% of what you need to solve the problem of [LRU Cache](https://leetcode.com/articles/lru-cache/). #### Approach 1: Singly Linked List Let's start from the simplest possible MyLinkedList, which contains just a structure size and a sentinel head. ![bla](../Figures/707/singly4.png) Note, that sentinel node is used as a pseudo-head and is always present. This way the structure could never be empty, it will contain at least a sentinel head. All nodes in MyLinkedList have a type ListNode: value + link to the next element. **Add at Index, Add at Head and Add at Tail** Let's first discuss insert at index operation, because thanks to the sentinel node addAtTail and addAtHead operations could be reduced to this operation as well. The idea is straightforward: - Find the predecessor of the node to insert. If the node is to be inserted at head, its predecessor is a sentinel head. If the node is to be inserted at tail, its predecessor is the last node. - Insert the node by changing the link to the next node. ![bla](../Figures/707/singly_insert.png) --- ![bla](../Figures/707/singly_insert_head.png) **Delete at Index** Basically, the same as insert: - Find the predecessor. - Delete node by changing the links to the next node. ![bla](../Figures/707/singly_delete.png) **Get** Get is a very straightforward: start from the sentinel node and do `index + 1` steps ![bla](../Figures/707/singly_get.png) **Implementation** **Complexity Analysis** * Time complexity: $$\mathcal{O}(1)$$ for addAtHead. $$\mathcal{O}(k)$$ for get, addAtIndex, and deleteAtIndex, where $$k$$ is an index of the element to get, add or delete. $$\mathcal{O}(N)$$ for addAtTail. * Space complexity: $$\mathcal{O}(1)$$ for all operations.

--- #### Approach 2: Doubly Linked List Time to implement DLL MyLinkedList, which is a much faster (twice faster on the testcase set here) though a bit more complex. It contains size, sentinel head and sentinel tail. ![bla](../Figures/707/dll.png) Note, that sentinel head and tail are always present. All nodes in MyLinkedList have a type ListNode: value + two links: to the next and to the previous elements. **Add at Index, Add at Head and Add at Tail** The idea is simple: - Find the predecessor and the successor of the node to insert. If the node is to be inserted at head, its predecessor is a sentinel head. If the node is to be inserted at tail, its successor is a sentinel tail. > Use bidirectional search to perform faster. - Insert the node by changing the links to the next and previous nodes. ![bla](../Figures/707/dll_insert2.png) **Delete at Index** Basically, the same as insert: - Find the predecessor and successor. - Delete node by changing the links to the next and previous nodes. ![bla](../Figures/707/dll_delete2.png) **Get** Get is very straightforward: - Compare `index` and `size - index` to define the fastest way: starting from the head, or starting from the tail. - Go to the wanted node. ![bla](../Figures/707/dll_get2.png) **Implementation** **Complexity Analysis** * Time complexity: $$\mathcal{O}(1)$$ for addAtHead and addAtTail. $$\mathcal{O}(\min(k, N - k))$$ for get, addAtIndex, and deleteAtIndex, where $$k$$ is an index of the element to get, add or delete. * Space complexity: $$\mathcal{O}(1)$$ for all operations.

Design Linked List

Problem Description

Problem Description

Answer Panel