## Algorithm

Problem Name: 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 `index` equals 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
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]

Explanation
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`.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
var MyLinkedList = function() {
this.arr = []
}

MyLinkedList.prototype.get = function(index) {
if (this.arr[index] !== undefined) {
return this.arr[index]
} else {
return -1
}
}

this.arr.unshift(val)
}

this.arr.push(val)
}

if (this.arr.length >= index) {
this.arr.splice(index, 0, val)
}
if (index < 0) {
this.arr.unshift(val)
}
}

MyLinkedList.prototype.deleteAtIndex = function(index) {
if (index >= 0 && index < this.arr.length) {
this.arr.splice(index, 1)
}
}
``````
Copy The Code &

Input

cmd

Output

cmd

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Node:
def __init__(self, value):
self.val = value
self.next = self.pre = None

def __init__(self):
self.head = self.tail = Node(-1)
self.size = 0

def add(self, preNode, val):
node = Node(val)
node.pre = preNode
node.next = preNode.next
node.pre.next = node.next.pre = node
self.size += 1

def remove(self, node):
node.pre.next = node.next
node.next.pre = node.pre
self.size -= 1

def forward(self, start, end, cur):
while start != end:
start += 1
cur = cur.next
return cur

def backward(self, start, end, cur):
while start != end:
start -= 1
cur = cur.pre
return cur

def get(self, index):
if 0 <= index <= self.size // 2:
return self.forward(0, index, self.head.next).val
elif self.size // 2 < index < self.size:
return self.backward(self.size - 1, index, self.tail.pre).val
return -1

def addAtIndex(self, index, val):
if 0 <= index <= self.size // 2:
elif self.size // 2 < index <= self.size:
self.add(self.backward(self.size, index, self.tail).pre, val)

def deleteAtIndex(self, index):
if 0 <= index <= self.size // 2:
elif self.size // 2 < index < self.size:
self.remove(self.backward(self.size - 1, index, self.tail.pre))
``````
Copy The Code &

Input

cmd