欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python實現(xiàn)單項鏈表的最全教程

 更新時間：2023年01月07日 08:53:45   作者：Thank?CAT  
單向鏈表也叫單鏈表，是鏈表中最簡單的一種形式，它的每個節(jié)點包含兩個域，一個信息域（元素域）和一個鏈接域，這個鏈接指向鏈表中的下一個節(jié)點，而最后一個節(jié)點的鏈接域則指向一個空值，這篇文章主要介紹了Python實現(xiàn)單項鏈表,需要的朋友可以參考下

單向鏈表

單向鏈表也叫單鏈表，是鏈表中最簡單的一種形式，它的每個節(jié)點包含兩個域，一個信息域（元素域）和一個鏈接域。這個鏈接指向鏈表中的下一個節(jié)點，而最后一個節(jié)點的鏈接域則指向一個空值。

  • 表元素域elem用來存放具體的數(shù)據(jù)。
  • 鏈接域next用來存放下一個節(jié)點的位置（python中的標識）
  • 變量p指向鏈表的頭節(jié)點（首節(jié)點）的位置，從p出發(fā)能找到表中的任意節(jié)點。

節(jié)點實現(xiàn)

class Node(object):
    """節(jié)點"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None

單鏈表的操作

  • is_empty() 鏈表是否為空
  • length() 鏈表長度
  • travel() 遍歷整個鏈表
  • add(item) 鏈表頭部添加元素
  • append(item) 鏈表尾部添加元素
  • insert(pos, item) 指定位置添加元素
  • remove(item) 刪除節(jié)點
  • search(item) 查找節(jié)點是否存在

單鏈表的實現(xiàn)

class SingleLinkList(object):
    """單鏈表"""
    def __init__(self, node=None):
        self.__head = node

單鏈表 判斷鏈表是否為空（is_empty）

def is_empty(self):
        """鏈表是否為空"""
        return self.__head == None

單鏈表 鏈表長度（length）

def length(self):
        """鏈表長度"""
        # cur游標，用來移動遍歷節(jié)點
        cur = self.__head
        # count記錄數(shù)量
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

單鏈表 遍歷整個鏈表（travel）

def travel(self):
        """遍歷整個鏈表"""
        cur = self.__head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next
        print("")

單鏈表 鏈表尾部添加元素，尾插法（append）

def append(self, item):
        """鏈表尾部添加元素, 尾插法"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

單鏈表 鏈表頭部插入元素，頭插法（add）

def add(self, item):
        """鏈表頭部添加元素，頭插法"""
        node = Node(item)
        node.next = self.__head
        self.__head = node

單鏈表 指定位置插入元素（insert）

def insert(self, pos, item):
        """指定位置添加元素
        :param  pos 從0開始
        """
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < (pos-1):
                count += 1
                pre = pre.next
            # 當循環(huán)退出后，pre指向pos-1位置
            node = Node(item)
            node.next = pre.next
            pre.next = node

單鏈表 刪除節(jié)點（remove）

def remove(self, item):
        """刪除節(jié)點"""
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 先判斷此結點是否是頭節(jié)點
                # 頭節(jié)點
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

單鏈表 查找節(jié)點是否存在（search）

def search(self, item):
        """查找節(jié)點是否存在"""
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

單鏈表 完整代碼及測試

# coding:utf-8

class Node(object):
    """節(jié)點"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    """單鏈表"""
    def __init__(self, node=None):
        self.__head = node

    def is_empty(self):
        """鏈表是否為空"""
        return self.__head == None

    def length(self):
        """鏈表長度"""
        # cur游標，用來移動遍歷節(jié)點
        cur = self.__head
        # count記錄數(shù)量
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍歷整個鏈表"""
        cur = self.__head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next
        print("")

    def add(self, item):
        """鏈表頭部添加元素，頭插法"""
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        """鏈表尾部添加元素, 尾插法"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        """指定位置添加元素
        :param  pos 從0開始
        """
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < (pos-1):
                count += 1
                pre = pre.next
            # 當循環(huán)退出后，pre指向pos-1位置
            node = Node(item)
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        """刪除節(jié)點"""
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 先判斷此結點是否是頭節(jié)點
                # 頭節(jié)點
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

    def search(self, item):
        """查找節(jié)點是否存在"""
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False



if __name__ == "__main__":
    ll = SingleLinkList()
    print(ll.is_empty())
    print(ll.length())

    ll.append(1)
    print(ll.is_empty())
    print(ll.length())


    ll.append(2)
    ll.add(8)
    ll.append(3)
    ll.append(4)
    ll.append(5)
    ll.append(6)
    # 8 1 2 3 4 5 6
    ll.insert(-1, 9) # 9 8 1 23456
    ll.travel()
    ll.insert(3, 100) # 9 8 1 100 2 3456
    ll.travel()
    ll.insert(10, 200) # 9 8 1 100 23456 200
    ll.travel()
    ll.remove(100)
    ll.travel()
    ll.remove(9)
    ll.travel()
    ll.remove(200)
    ll.travel()
"""
result:
True
0
False
1
9 8 1 2 3 4 5 6 
9 8 1 100 2 3 4 5 6 
9 8 1 100 2 3 4 5 6 200 
9 8 1 2 3 4 5 6 200 
8 1 2 3 4 5 6 200 
8 1 2 3 4 5 6 
"""

鏈表與順序表的對比

鏈表失去了順序表隨機讀取的優(yōu)點，同時鏈表由于增加了結點的指針域，空間開銷比較大，但對存儲空間的使用要相對靈活。

鏈表與順序表的各種操作復雜度如下所示：

操作鏈表順序表
訪問元素O(n)O(1)
在頭部插入/刪除O(1)O(n)
在尾部插入/刪除O(n)O(1)
在中間插入/刪除O(n)O(n)

注意雖然表面看起來復雜度都是 O(n)，但是鏈表和順序表在插入和刪除時進行的是完全不同的操作。鏈表的主要耗時操作是遍歷查找，刪除和插入操作本身的復雜度是O(1)。順序表查找很快，主要耗時的操作是拷貝覆蓋。因為除了目標元素在尾部的特殊情況，順序表進行插入和刪除時需要對操作點之后的所有元素進行前后移位操作，只能通過拷貝和覆蓋的方法進行。

到此這篇關于Python實現(xiàn)單項鏈表的最全教程的文章就介紹到這了,更多相關Python實現(xiàn)單項鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

最新評論