鏈表是一種由節(jié)點(diǎn)組成的線性數(shù)據(jù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素和一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針。P5228資訊網(wǎng)——每日最新資訊28at.com

P5228資訊網(wǎng)——每日最新資訊28at.com

1.鏈表的基本概念

(1)節(jié)點(diǎn)定義P5228資訊網(wǎng)——每日最新資訊28at.com

鏈表中的每一個(gè)元素都是一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)通常包含兩部分：數(shù)據(jù)和下一個(gè)節(jié)點(diǎn)的引用。P5228資訊網(wǎng)——每日最新資訊28at.com

class Node:    def __init__(self, data):        self.data = data  # 節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)        self.next = None  # 默認(rèn)下一個(gè)節(jié)點(diǎn)為空

(2)鏈表定義P5228資訊網(wǎng)——每日最新資訊28at.com

鏈表通常有一個(gè)頭節(jié)點(diǎn)來(lái)表示鏈表的開(kāi)始。尾節(jié)點(diǎn)是鏈表中的最后一個(gè)節(jié)點(diǎn)，它的下一個(gè)節(jié)點(diǎn)引用為None。P5228資訊網(wǎng)——每日最新資訊28at.com

P5228資訊網(wǎng)——每日最新資訊28at.com

class LinkedList:    def __init__(self):        self.head = None  # 初始鏈表為空

2.向鏈表中添加元素

(1)在鏈表的開(kāi)頭添加元素P5228資訊網(wǎng)——每日最新資訊28at.com

def add_first(self, data):    new_node = Node(data)   # 創(chuàng)建新的節(jié)點(diǎn)    new_node.next = self.head  # 將新節(jié)點(diǎn)指向當(dāng)前的頭節(jié)點(diǎn)    self.head = new_node    # 更新頭節(jié)點(diǎn)為新節(jié)點(diǎn)LinkedList.add_first = add_first

(2)在鏈表的結(jié)尾添加元素P5228資訊網(wǎng)——每日最新資訊28at.com

def add_last(self, data):    new_node = Node(data)    if self.head is None:  # 若鏈表為空，則直接將新節(jié)點(diǎn)設(shè)置為頭節(jié)點(diǎn)        self.head = new_node        return    last_node = self.head  # 遍歷到鏈表的尾部    while last_node.next:        last_node = last_node.next    last_node.next = new_node  # 在鏈表尾部添加新節(jié)點(diǎn)LinkedList.add_last = add_last

3.從鏈表中刪除元素

(1)刪除鏈表的第一個(gè)元素P5228資訊網(wǎng)——每日最新資訊28at.com

def remove_first(self):    if self.head:        self.head = self.head.next  # 更新頭節(jié)點(diǎn)為下一個(gè)節(jié)點(diǎn)LinkedList.remove_first = remove_first

(2)刪除鏈表的最后一個(gè)元素P5228資訊網(wǎng)——每日最新資訊28at.com

def remove_last(self):    if self.head is None:  # 若鏈表為空，直接返回        return    if self.head.next is None:  # 若鏈表只有一個(gè)元素，將頭節(jié)點(diǎn)設(shè)置為空        self.head = None        return    second_to_last = self.head  # 找到倒數(shù)第二個(gè)節(jié)點(diǎn)    while second_to_last.next.next:        second_to_last = second_to_last.next    second_to_last.next = None  # 將倒數(shù)第二個(gè)節(jié)點(diǎn)的next設(shè)置為空，從而刪除最后一個(gè)節(jié)點(diǎn)LinkedList.remove_last = remove_last

4.遍歷鏈表

def print_list(self):    current_node = self.head  # 從頭節(jié)點(diǎn)開(kāi)始遍歷    while current_node:        print(current_node.data, end=" -> ")        current_node = current_node.next  # 移動(dòng)到下一個(gè)節(jié)點(diǎn)    print("None")LinkedList.print_list = print_list

5.查找鏈表中的元素

def search(self, target):    current_node = self.head  # 從頭節(jié)點(diǎn)開(kāi)始遍歷    while current_node:        if current_node.data == target:  # 若找到目標(biāo)數(shù)據(jù)，返回True            return True        current_node = current_node.next  # 移動(dòng)到下一個(gè)節(jié)點(diǎn)    return False  # 遍歷完鏈表后，未找到目標(biāo)數(shù)據(jù)，返回FalseLinkedList.search = search

6.實(shí)戰(zhàn)案例：反轉(zhuǎn)鏈表一個(gè)常見(jiàn)的面試問(wèn)題是如何反轉(zhuǎn)鏈表。我們可以使用迭代的方法來(lái)解決這個(gè)問(wèn)題。P5228資訊網(wǎng)——每日最新資訊28at.com

def reverse(self):    prev = None  # 上一個(gè)節(jié)點(diǎn)    current = self.head  # 當(dāng)前節(jié)點(diǎn)    while current:        next_node = current.next  # 記錄下一個(gè)節(jié)點(diǎn)        current.next = prev  # 將當(dāng)前節(jié)點(diǎn)指向上一個(gè)節(jié)點(diǎn)        prev = current  # 更新上一個(gè)節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)        current = next_node  # 移動(dòng)到下一個(gè)節(jié)點(diǎn)    self.head = prev  # 更新頭節(jié)點(diǎn)LinkedList.reverse = reverse# 使用示例ll = LinkedList()ll.add_last(1)ll.add_last(2)ll.add_last(3)ll.print_list()  # 輸出：1 -> 2 -> 3 -> Nonell.reverse()ll.print_list()  # 輸出：3 -> 2 -> 1 -> None

小結(jié)

鏈表提供了一種在內(nèi)存中存儲(chǔ)有序元素的方法，它的主要優(yōu)勢(shì)在于插入和刪除操作的效率高，不需要移動(dòng)其他元素。不過(guò)，鏈表的隨機(jī)訪問(wèn)速度比數(shù)組慢，因?yàn)樾枰獜念^節(jié)點(diǎn)開(kāi)始遍歷。理解鏈表的結(jié)構(gòu)和常用操作是計(jì)算機(jī)科學(xué)基礎(chǔ)，也經(jīng)常用于面試中。P5228資訊網(wǎng)——每日最新資訊28at.com

本文鏈接：http://www.www897cc.com/showinfo-26-12388-0.html五分鐘搞懂鏈表實(shí)現(xiàn)：Python數(shù)據(jù)結(jié)構(gòu)與算法

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com

上一篇： 七個(gè)國(guó)外高效開(kāi)發(fā)者工具，讓你的工作流程比德芙更加絲滑

下一篇： 僅需五分鐘，使用Initializr快速開(kāi)發(fā)Spring Boot應(yīng)用