連結串列一般指的是單向連結串列(Single Linked List),由node
所組成,每個node
都具有兩種屬性,分別是「資料」以及「指標」。資料是儲存目前這個節點的值,指標是指向下一個節點的連結,至於最後一個結點則會指向null
。
連結串列比起一般的陣列,優點是能夠隨著需求動態配置記憶體,插入或移除元素時也相對方便;缺點是取出元素時無法直接指定位置,需要遍歷整個串列。
以下用python
來實作Linked List
。
首先我們要實作node
,宣告一個class
名稱ListNode
,每個node
都需要兩個元素,資料value
與指向下一個node
的指標next
。
1 2 3 4
| class ListNode(object): def __init__(self, value=None, next=None): self.val = value self.next = next
|
我們還要宣告一個名為LinkedList
的類別,用來紀錄串列的起始位置。
1 2 3
| class LinkedList(object): def __init__(self, head=None): self.head = head
|
接著在LinkedList
實作下面的方法:
- print_nodes()
- at(index)
- append(value)
- insert(index, value)
- removePos(index)
- remove(value, all=False)
- indexOf(value)
- clear()
- isEmpty()
- size()
首先是print_nodes
方法,走訪所有的節點並印出每個結點的資料。
1 2 3 4 5 6 7 8
| def print_nodes(self): if not self.head: print(self.head) node = self.head while node: end = " -> " if node.next else "\n" print(node.val, end=end) node = node.next
|
接著是at
方法,回傳index
位置的value
。
1 2 3 4 5 6 7 8
| def at(self, index): count = 0 node = self.head while node: if count == index: return node.val count += 1 node = node.next
|
第三個是append
,將值為value
的節點接在陣列的最尾端。
1 2 3 4 5 6 7 8
| def append(self, value): if not self.head: self.head = ListNode(value) return node = self.head while node.next: node = node.next node.next = ListNode(value)
|
第四個是insert
,將value
插入index
的位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| def insert(self, index, value): if index >= self.size(): self.append(value) return count = 0 node = self.head previous = None while node: if count == index: if previous: new_node = ListNode(value, previous.next) previous.next = new_node else: self.head = ListNode(value, node) return count += 1 previous = node node = node.next
|
第五個與第六個是removePos
以及remove
,分別是移除位置為index
的節點,以及移除值為value
的節點。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| def removePos(self, index): count = 0 node = self.head previous = None while node: if count == index: if previous: previous.next = node.next node = node.next else: self.head = node.next node = self.head return else: previous = node node = node.next
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| def remove(self, val, all=False): node = self.head previous = None while node: if node.val == val: if previous: previous.next = node.next node = node.next else: self.head = node.next node = self.head if not all: return else: previous = node node = node.next
|
第七個是indexOf
,回傳第一個出現的value
在串列中的的位置。
1 2 3 4 5 6 7 8
| def indexOf(self, value): node = self.head count = 0 while node: if node.val == value: return count count += 1 node = node.next
|
最後三個是clear
, isEmpty
, 以及size
。
1 2
| def clear(self): self.head = None
|
1 2
| def isEmpty(self): return self.head is None
|
1 2 3 4 5 6 7
| def size(self): count = 0 node = self.head while node: count += 1 node = node.next return count
|
程式碼連結