亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

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

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

單向鏈表

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

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

節(jié)點(diǎn)實(shí)現(xiàn)

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

單鏈表的操作

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

單鏈表的實(shí)現(xiàn)

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

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

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

單鏈表 鏈表長(zhǎng)度（length）

def length(self):
        """鏈表長(zhǎng)度"""
        # cur游標(biāo)，用來(lái)移動(dòng)遍歷節(jié)點(diǎn)
        cur = self.__head
        # count記錄數(shù)量
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

單鏈表 遍歷整個(gè)鏈表（travel）

def travel(self):
        """遍歷整個(gè)鏈表"""
        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
            # 當(dāng)循環(huán)退出后，pre指向pos-1位置
            node = Node(item)
            node.next = pre.next
            pre.next = node

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

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

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

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

單鏈表 完整代碼及測(cè)試

# coding:utf-8

class Node(object):
    """節(jié)點(diǎn)"""
    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):
        """鏈表長(zhǎng)度"""
        # cur游標(biāo)，用來(lái)移動(dòng)遍歷節(jié)點(diǎn)
        cur = self.__head
        # count記錄數(shù)量
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍歷整個(gè)鏈表"""
        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
            # 當(dāng)循環(huán)退出后，pre指向pos-1位置
            node = Node(item)
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        """刪除節(jié)點(diǎn)"""
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 先判斷此結(jié)點(diǎn)是否是頭節(jié)點(diǎn)
                # 頭節(jié)點(diǎn)
                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é)點(diǎn)是否存在"""
        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 
"""

鏈表與順序表的對(duì)比

鏈表失去了順序表隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開銷比較大，但對(duì)存儲(chǔ)空間的使用要相對(duì)靈活。

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

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

注意雖然表面看起來(lái)復(fù)雜度都是 O(n)，但是鏈表和順序表在插入和刪除時(shí)進(jìn)行的是完全不同的操作。鏈表的主要耗時(shí)操作是遍歷查找，刪除和插入操作本身的復(fù)雜度是O(1)。順序表查找很快，主要耗時(shí)的操作是拷貝覆蓋。因?yàn)槌四繕?biāo)元素在尾部的特殊情況，順序表進(jìn)行插入和刪除時(shí)需要對(duì)操作點(diǎn)之后的所有元素進(jìn)行前后移位操作，只能通過拷貝和覆蓋的方法進(jìn)行。

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

相關(guān)文章

最新評(píng)論