#### 单链表 ``` 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 指的是元素的索引。