連結串列(Linked List)

2017-09-02
#Python #Linked List
學校課程/ 資料結構

連結串列一般指的是單向連結串列(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實作下面的方法：

  1. print_nodes()
  2. at(index)
  3. append(value)
  4. insert(index, value)
  5. removePos(index)
  6. remove(value, all=False)
  7. indexOf(value)
  8. clear()
  9. isEmpty()
  10. 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

程式碼連結