天天看點
傳回

資料結構與算法 4.連結清單 LinkList

連結清單 LinkList 

定義：連結清單是由一系列節點組成的元素集合
每個節點node包含兩部分：資料域item和指向下一節點的指針next，雙向連結清單還有指向上一節點的指針prev
連結清單是一種鍊式存儲的線性表，所有元素的記憶體位址不一定是連續的
連結清單可以做到用多少空間就申請多少存儲空間

分類：單連結清單，循環連結清單，雙向連結清單

連結清單的接口設計：
    isEmpty()           判斷連結清單是否為空
    length()            傳回連結清單的長度
    travel()            周遊連結清單
    add(item)           在頭部添加節點
    append(item)        在尾部添加節點
    insert(pos,item)    在指定位置添加節點
    remove(item)        删除節點
    search(item)        查找節點是否存在

連結清單 與 順序表 同一操作的時間複雜度
    通路元素：n 1
    頭部添加：1 n
    尾部添加：n 1
    中間添加：n n

單連結清單

定義機關元素 
class Node(object):
    def __init__(self,item):
        self.item = item
        self.next = None
定義單連結清單 
class LinkList(object):
    def __init__(self):
        self.head = None

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

    # 擷取連結清單長度，在周遊連結清單的過程中記錄節點數量
    def length(self):
        cur = self.head

        count = 0
        while cur != None :
            count += 1
            cur = cur.next
        return count

    # 周遊連結清單
    def travel(self):
        cur = self.head
        while cur :
            print(cur.item)
            cur = cur.next
        return None

    # 在連結清單頭部添加節點
    def addFirst(self,item):
        node = Node(item)
        # 無論連結清單是否為空
        node.next = self.head
        self.head = node

    # 在連結清單尾部添加節點
    def append(self,item):
        node = Node(item)

        cur = self.head
        # 如果連結清單為空，添加的節點既是首節點也是尾節點
        if self.isEmpty():
            self.head = node
        # 連結清單不為空，先周遊，再添加
        else :
            cur = self.head
            while cur.next :
                cur = cur.next
            cur.next = node

    # 在連結清單指定位置添加節點
    def insert(self,pos,item):
        # 添加的位置小于1，調用添加首節點的方法
        if pos <= 0 :
            self.addFirst(item)
        # 添加的位置大于連結清單長度-1，調用添加尾節點的方法
        elif pos > (self.length() - 1) :
            self.append(item)
        # 插入到連結清單中間位置，使用count記錄指針移動的位置
        else :
            node = Node(item)
            count = 0
            pre = self.head
            # 移動到插入位置前面時，循環結束
            while count < (pos - 1) :
                count += 1
                pre = pre.next
            node.next = pre.next
            pre.next = node

    # 删除節點
    def remove(self,item):
        # 建立副指針pre，始終在主指針cur後面一個位置
        cur = self.head
        pre = None
        # 周遊連結清單，直至找到要删除的節點
        while cur != None :
            # 目前節點是要删除的節點
            if cur.item == item :
                # 要删除的節點是首節點，直接設定為None
                if not pre :
                    self.head = cur.next
                # 把被删除節點的前後兩個節點相連
                else :
                    pre.next = cur.next
                break
            # 目前節點不是要删除的節點，分别移動兩個指針
            else :
                pre = cur
                cur = cur.next

    # 查找節點是否存在
    def search(self,item):
        cur = self.head
        # 周遊連結清單，逐一對比元素的值
        while cur != None :
            if cur.item == item :
                return True
            cur = cur.next
        return False

單向循環連結清單

定義機關元素 
class Node(object):
    def __init__(self,item):
        self.item = item
        self.next = None
定義循環連結清單 
class CirLinkList(object):
    def __init__(self):
        self.head = None

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

    # 擷取連結清單長度
    def length(self):
        if self.isEmpty() :
            return 0

        count = 1
        cur = self.head
        while cur.next != self.head :
            count += 1
            cur = cur.next
        return count

    # 周遊連結清單
    def travel(self):
        if self.isEmpty() :
            return

        cur = self.head
        print(cur.item)
        while cur.next != self.head :
            cur = cur.next
            print(cur.item)

    # 在連結清單頭部添加節點
    def addFirst(self,item):
        node = Node(item)

        # 連結清單為空則添加的節點就是首節點
        if self.isEmpty() :
            self.head = node
            node.next = self.head
        # 連結清單不為空，先把節點連接配接到首節點，再把尾節點的.next從原首節點換到新節點
        else:
            node.next = self.head
            cur = self.head
            while cur.next != self.head :
                cur = cur.next
            cur.next = node
            self.head = node

    # 在連結清單尾部添加節點
    def append(self,item):
        node = Node(item)

        # 連結清單為空則添加的節點就是尾節點
        if self.isEmpty() :
            self.head = node
            node.next = self.head
        # 連結清單不為空，先把尾節點的.next從原首節點換到新節點，再把新節點與首節點相連
        else:
            cur = self.head
            while cur.next != self.head :
                cur = cur.next
            cur.next = node
            node.next = self.head

    # 在指定位置添加節點
    def insert(self,pos,item):
        # 添加位置小于1，調用添加首節點的方法
        if pos <= 0 :
            self.addFirst(item)
        # 添加位置大于連結清單長度-1，調用添加尾節點的方法
        elif pos > (self.length() - 1) :
            self.append(item)
        # 插入到連結清單中間位置，用ind記錄指針移動的位置，在添加位置的前一個節點停下，先連接配接，再斷開
        else:
            node = Node(item)
            cur = self.head
            ind = 0
            while ind < (pos - 1) :
                ind += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    # 删除節點
    def remove(self,item):
        if self.isEmpty() :
            return

        cur = self.head
        # 判斷要删除的節點是否為首節點
        if cur.item == item :
            # 删除首節點，判斷連結清單是否隻有一個節點
            if cur.next != self.head :
                # 有多個節點，把尾節點與第二個節點相連，再把第二個節點設為首節點
                while cur.next != self.head :
                    cur = cur.next
                cur.next = self.head.next
                self.head = self.head.next
            # 隻有一個節點，直接删除
            else:
                self.head = None
        # 要删除的節點不是首節點
        # 再建立一個指針副pre，始終在主指針cur後面一個位置
        else :
            pre = self.head
            while cur.next != self.head :
                pre = cur
                cur = cur.next
                # cur到達要删除節點的位置時，連接配接前後兩個節點
                if cur.item == item :
                    pre.next = cur.next
                    return

    # 搜尋節點是否存在
    def search(self,item):
        if self.isEmpty() :
            return False

        # 判斷搜尋的元素是否在首節點
        cur = self.head
        if cur.item == item :
            return True
        # 在周遊過程中逐一對比
        while cur.next != self.head :
            cur = cur.next
            if cur.item == item :
                return True
        return False

雙向連結清單

定義機關元素 
class Node(object):
    def __init__(self,item):
        self.item = item
        self.next = None
        self.prev = None
定義雙向連結清單 
class DouLinkList(object):
    def __init__(self):
        self.head = None

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

    # 擷取連結清單長度
    def length(self):
        if self.isEmpty() :
            return 0

        count = 0
        cur = self.head
        while cur != None :
            count += 1
            cur = cur.next
        return count

    # 周遊連結清單
    def travel(self):
        if self.isEmpty():
            return

        cur = self.head
        while cur != None :
            print(cur.item)
            cur = cur.next

    # 在連結清單頭部添加節點
    def addFirst(self,item):
        node = Node(item)

        if self.isEmpty() :
            self.head = node
        else :
            # 先建立連接配接，再修改節點的值
            node.next = self.head
            self.head.prev = node
            self.head = node

    # 在連結清單尾部添加節點
    def append(self,item):
        node = Node(item)

        if self.isEmpty() :
            self.head = node
        else :
            # 周遊連結清單直到尾節點，然後設定.next和.prev，使兩個節點相連
            cur = self.head
            while cur.next != None :
                cur = cur.next
            cur.next = node
            node.prev = cur

    # 在指定位置添加節點
    def insert(self,pos,item):
        # 添加位置小于1，調用添加首節點的方法
        if pos <= 0 :
            self.addFirst(item)
        # 添加位置大于連結清單長度-1，調用添加尾節點的方法
        elif pos > (self.length() - 1) :
            self.append(item)
        # 添加到連結清單中間位置
        else :
            # 使用ind記錄指針移動的位置
            node = Node(item)
            cur = self.head
            ind = 0
            # 到達添加位置前面時循環結束
            while ind < (pos - 1) :
                ind += 1
                cur = cur.next
            # 先連接配接，後斷開
            node.next = cur.next
            node.prev = cur
            cur.next.prev = node
            cur.next = node

    # 删除節點，把被删除節點的前後兩個節點互相連接配接，即完成删除
    def remove(self,item):
        if self.isEmpty() :
            return

        cur = self.head
        # 要删除的節點是首節點，則判斷連結清單長度
        if cur.item == item :
            # 連結清單隻有一個節點，直接删除
            if cur.next == None :
                self.head = None
            # 連結清單有多個節點，把第二個節點設為首節點
            else :
                cur.next.prev = None
                self.head = cur.next
            return
        # 要删除的節點不是首節點
        else :
            while cur != None :
                # 找到要删除的節點時，先将其前一個節點的.next指向其後一個節點
                if cur.item == item:
                    # 再判斷要删除的是否為尾節點，是則直接删除
                    cur.prev.next = cur.next
                    if cur.next == None :
                        cur = None
                        return
                    # 不是則将其後一個節點的.prev指向其前一個節點
                    else :
                        cur.next.prev = cur.prev
                cur = cur.next

    # 搜尋節點是否存在于連結清單
    def search(self,item):
        if self.isEmpty() :
            return False
        
        # 周遊連結清單，逐一判斷元素值
        cur = self.head
        while cur != None :
            if cur.item == item :
                return True
            else :
                cur = cur.next
        return False
連結清單 添加節點 删除節點 雙向連結清單 指定位置
上一篇: 資料結構與算法 5.樹
下一篇: 資料結構與算法 3.隊列 Queue

繼續閱讀