資料結構 之 '連結清單'

python實作連結清單的基本操作

連結清單

連結清單是一種實體存儲單元上非連續、非順序的存儲結構，資料元素的邏輯順序是通過連結清單中的指針連結次序實作的。連結清單由一系列結點（連結清單中每一個元素稱為結點）組成，結點可以在運作時動态生成。每個結點包括兩個部分：一個是存儲資料元素的資料域，另一個是存儲下一個結點位址的指針域。 相比于線性表順序結構，操作複雜。由于不必須按順序存儲，連結清單在插入的時候可以達到O(1)的複雜度，比另一種線性表順序表快得多，但是查找一個節點或者通路特定編号的節點則需要O(n)的時間，而線性表和順序表相應的時間複雜度分别是O(logn)和O(1)。

基本操作

class Node(object):
    """
    封裝節點
    """
    def __init__(self, item):
        # 存儲資料元素的資料域
        self.item = item

        # 存儲下一個結點位址的指針域
        self.next = None


class Link(object):
    """
    封裝連結清單
    """
    def __init__(self):
        # 初始化一個空連結清單
        self._head = None
        # '_head' 用于指向連結清單的第一個節點

    def add(self, item):
        """
        連結清單首部插入節點
        :param item:
        :return:
        """
        node = Node(item)
        node.next = self._head
        self._head = node

    def travel(self):
        """
        周遊每一個節點
        :return:
        """
        cur = self._head
        while cur:
            print(cur.item)
            cur = cur.next

    def length(self):
        """
        連結清單中節點的個數
        :return:
        """
        count_node = 0
        cur = self._head
        while cur:
            count_node += 1
            cur = cur.next
        return count_node

    def isEmpty(self):
        """
        判斷連結清單是否為空
        :return:
        """
        return self._head == None

    def search(self, item):
        """
        查找是否存在item對應的節點
        :param item:
        :return:
        """
        find = False
        cur = self._head
        while cur:
            if cur.item == item:
                find = True
                break
            else:
                cur = cur.next
        return find

    def append(self, item):
        """
        連結清單的尾部插入節點
        :param item:
        :return:
        """
        node = Node(item)
        if self._head == None:
            self._head = node
            return

        cur = self._head
        pre = None
        while cur:
            pre = cur
            cur = cur.next
        pre.next = node

    def insert(self, pos, item):
        """
        連結清單中指定的位置插入新的節點
        :param pos:
        :param item:
        :return:
        """
        node = Node(item)
        if pos == 0:
            node.next = self._head
            self._head = node
            return
        pre = None
        cur = self._head
        for i in range(pos):
            pre = cur
            cur = cur.next
        pre.next = node
        node.next = cur

    def remove(self, item):
        """
        删除節點
        :param item: 
        :return: 
        """
        cur = self._head
        pre = None

        if cur.item == item:
            self._head = cur.next
            return
        while True:
            pre = cur
            cur = cur.next
            if cur.item == item:
                pre.next = cur.next
                break
            if cur == None:
                break

    def reverse(self):
        """
        連結清單倒置
        :return: 
        """
        pre = None
        cur = self._head
        next_node = cur.next

        while cur:
            cur.next = pre
            pre = cur
            cur = next_node
            if cur != None:
                next_node = next_node.next
        self._head = pre
        self.travel()


if __name__ == '__main__':
    link = Link()
    link.append(1)
    link.append(2)
    link.append(3)
    link.append(4)
    link.reverse()
    

# 4
# 3
# 2
# 1

           

抟扶搖而上者九萬裡