#### 单链表
```
class ListNode:
def __init__(self, x: int):
self.val = x
self.next = None
class MyLinkedList:
def __init__(self):
self.head = ListNode(0)
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
curr = self.head
for _ in range(index + 1):
curr = curr.next
return curr.val
def addAtHead(self, val: int) -> None:
self.addAtIndex(0, val)
def addAtTail(self, val: int) -> None:
self.addAtIndex(self.size, val)
def addAtIndex(self, index: int, val: int) -> None:
if index > self.size:
return
if index < 0:
index = 0
self.size += 1
pre = self.head
for _ in range(index):
pre = pre.next
newNode = ListNode(val)
newNode.next = pre.next
pre.next = newNode
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
self.size -= 1
pre = self.head
for _ in range(index):
pre = pre.next
pre.next = pre.next.next
```
##### 时间复杂度
- addAtHead:O(1)
- addAtIndex,get,deleteAtIndex: O(k), k 指的是元素的索引。
- addAtTail:O(N),其中 N 指的是链表的元素个数。
#### 双向链表
```
#!/usr/bin/env python3
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
self.prev = None
class MyLinkedList:
def __init__(self):
self.size = 0
self.head, self.tail = ListNode(0), ListNode(0)
self.head.next = self.tail
self.tail.prev = self.head
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
#选最快一端遍历
if index + 1 < self.size - index:
curr = self.head
for _ in range(index + 1):
curr = curr.next
else:
curr = self.tail
for _ in range(self.size - index):
curr = curr.prev
return curr.val
def addAtHead(self, val: int) -> None:
pred, succ = self.head, self.head.next
self.size += 1
newNode = ListNode(val)
newNode.prev = pred
newNode.next = succ
pred.next = newNode
succ.prev = newNode
def addAtTail(self, val: int) -> None:
succ, pred = self.tail, self.tail.prev
self.size += 1
newNode = ListNode(val)
newNode.next = succ
newNode.prev = pred
pred.next = newNode
succ.prev = newNode
def addAtIndex(self, index: int, val: int) -> None:
if index > self.size:
return
if index < 0:
index = 0
if index < self.size - index:
pred = self.head
for _ in range(index):
pred = pred.next
succ = pred.next
else:
succ = self.tail
for _ in range(self.size - index):
succ = succ.prev
pred = succ.prev
self.size += 1
newNode = ListNode(val)
newNode.prev = pred
newNode.next = succ
pred.next = newNode
succ.prev = newNode
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
if index < self.size - index:
pred = self.head
for _ in range(index):
pred = pred.next
succ = pred.next.next
else:
succ = self.tail
for _ in range(self.size - index - 1):
succ = succ.prev
pred = succ.prev.prev
self.size -= 1
pred.next = succ
succ.prev = pred
```
##### 时间复杂度
- addAtHead,addAtTail: O(1)
- addAtIndex,get,deleteAtIndex: O(min(k ,n-k)), k 指的是元素的索引。