鏈結串列(Linked List)

鏈結串列(Linked List)

Author: Jed. Feb 05, 2025

鏈結串列(Linked List)

鏈結串列為重要數據結構之一，用於動態管理數據，且元素在記憶體中是不連續儲存的，而是用指標進行連接，這種特性優勢在於頻繁操作插入與刪除的情境。

什麼是指標?

引用維基百科解釋: 在電腦科學中，指標（英語：Pointer），是在許多程式語言中用來儲存記憶體位址的變數。指標變數的值直接指向（points to）存在該位址的對象的值。所指向的可以是電腦主記憶體中的另一個值，或者在某些情況下，是主記憶體對映電腦硬體的值。

這邊簡單舉個例子

例子-大賣場

賣場中有商品與擺放商品架子以及指引，假設頻果放在3號架子，我們手中有商品查詢清單，將得知蘋果的位置(位址)

  1. 蘋果（商品） = 變數的值
    • 例如：string goods = "apple"; 中的 "apple"。
  2. 3 號架子（位置） = 變數的記憶體位址
    • 例如：&goods 可能是 0x7ffee436a6c。
  3. 商品查詢清單中的一筆紀錄 = 指標變數
    • 例如：string* pointer = &goods;
    • 這筆紀錄寫著：「蘋果在 3 號架子」(指的就是記憶體位址)。
    • 而 pointer 自己也是變數所以需的位址也會被儲存（如 0x7ffee436a6d）。指標就是一個專門用來儲存位址的變數。
  4. 透過紀錄找到蘋果 = 透過指標取值
    • 例如：pointer 會得到 "apple"（實際的蘋果）。

Linked List 操作

Read讀取

前文得知Linked List 在記憶體中為不連續儲存，而每條鏈都是指向一個記憶體位址，而讀取方式

  • 從 頭節點（起始節點）開始。
  • 檢查該節點的資料，然後通過節點中的指標（指向下一個節點的位址）跳轉到下一個節點。
  • 重複這個過程，直到到達最後一個節點。
  • 順序讀取。
graph LR A[apple] --> B[banana] B --> C[orange] C --> E[None]

透過python建立一個Linked List

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

apple = Node("apple")
banana = Node("banana")
orange = Node("orange")
apple.next = banana
banana.next = orange
ptr = apple

while ptr:
    print(ptr.data)
    ptr = ptr.next

image.png

由此程式可以看出依序讀取，所以得知在時間複雜度上是O(n)。

Insert插入

接著來實作插入，而插入我們在定義一個新的Class為LinkedList，接著實作insert。

class Node
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def print(self):
        ptr = self.head

        while ptr:
            print(ptr.data)
            ptr = ptr.next

    def insert_after(self, pre_node, value):
        value = Node(value)
        value.next = pre_node.next
        pre_node.next = value

linked_list = LinkedList()
linked_list.head = Node("apple")
banana = Node("banana")
orange = Node("orange")
linked_list.head.next = banana
banana.next = orange
linked_list.print()
print("插入結果")
linked_list.insert_after(banana, "pear")
linked_list.print()

image.png

來一一解釋，首先建立Linked List，有蘋果、香蕉、橘子。

graph LR A[apple] --> B[banana] B --> C[orange] C --> D[None]

接著插入梨子，這邊先將梨子指向orange記憶體位址。

graph LR A[apple] --> B[banana] B --> C[orange] C --> D[None] E[pear] E -->|插入指向orange| C[orange]

然後將更新香蕉指向梨子。

graph LR A[apple] --> B[banana] B -->|舊指向已被移除| C[orange] C --> D[None] %% 插入 `pear` 節點 B -->|更新成指向pear| E[pear] E --> C[orange]

最終結果梨子就被insert了。

graph LR A[apple] --> B[banana] B --> D[pear] D --> C[orange] C --> E[None]

在這實作中，插入是已知節點，所以時間複雜度是O(1)，但如果要插入未知位置，需要先遍歷鏈結串列找到插入位置，然後再進行插入操作，時間複雜度為 O(n)。

刪除

接著實作刪除，刪除以我們不知node位置，所以要先遍歷鏈結串列找到位置，再進行刪除。

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def print(self):
        ptr = self.head

        while ptr:
            print(ptr.data)
            ptr = ptr.next

    def insert_after(self, pre_node, value):
        value = Node(value)
        value.next = pre_node.next
        pre_node.next = value

    def delete(self, value):
        ptr = self.head
        # 如果頭節點是要刪除的節點
        if ptr and ptr.data == value:
            self.head = ptr.next
            ptr = None
            return

        prev = None
        # 找到節點並刪除
        while ptr and ptr.data != value:
            prev = ptr
            ptr = ptr.next

        if ptr is None:  # 沒有找到要刪除的節點
            return

        prev.next = ptr.next
        ptr = None

linked_list = LinkedList()
linked_list.head = Node("apple")
banana = Node("banana")
orange = Node("orange")
linked_list.head.next = banana
banana.next = orange
linked_list.print()
print("插入結果")
linked_list.insert_after(banana, "pear")
linked_list.print()

linked_list.delete('banana')
linked_list.print()

這個例子假如刪除是head時間複雜度為O(1)，但如果最壞情況遍歷鏈結串列找到刪除位置則是O(n)。

Circular Linked List

顧名思是就是將尾部指向頭部形成Circular Linked List。

graph LR A[apple] --> B[banana] B --> C[orange] C --> A[apple] 
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

apple = Node("apple")
banana = Node("banana")
orange = Node("orange")
apple.next = banana
banana.next = orange
orange.next = apple
ptr = apple
counter = 1

while counter <= 9:
    print(ptr.data)
    ptr = ptr.next
    counter += 1

Doubly Linked List

一開始介紹的Linked List是單向的，現在改成雙向只需多指回去反方向。

graph LR A[apple] <--> B[banana] <--> C[orange] 
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        self.prev = None  # 新增前一個節點的指標

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def print_forward(self):
        """正向輸出雙向鏈結串列"""
        ptr = self.head
        while ptr:
            print(ptr.data, end=" <-> ")
            ptr = ptr.next
        print("None")

    def print_backward(self):
        """反向輸出雙向鏈結串列"""
        ptr = self.head
        if not ptr:
            return
        while ptr.next:
            ptr = ptr.next  # 找到最後一個節點
        while ptr:
            print(ptr.data, end=" <-> ")
            ptr = ptr.prev
        print("None")

    def insert_after(self, pre_node, value):
        """在 pre_node 之後插入新節點"""
        new_node = Node(value)
        new_node.next = pre_node.next
        new_node.prev = pre_node

        if pre_node.next:
            pre_node.next.prev = new_node  # 更新原本後續節點的 prev 指標

        pre_node.next = new_node

# 初始化雙向鏈結串列
doubly_linked_list = DoublyLinkedList()
doubly_linked_list.head = Node("apple")
banana = Node("banana")
orange = Node("orange")

# 建立雙向連結
doubly_linked_list.head.next = banana
banana.prev = doubly_linked_list.head
banana.next = orange
orange.prev = banana

# 測試輸出
doubly_linked_list.print_forward()

print("插入 pear 之後：")
doubly_linked_list.insert_after(banana, "pear")
doubly_linked_list.print_forward()

# 測試反向輸出
print("反向輸出：")
doubly_linked_list.print_backward()

Linked List應用(discord 音樂播放機器人)

之前有玩過discord bot，這邊就來改用Linked List實作discord音樂機器人，首先進入discord申請api key。

Discord Developer Portal — API Docs for Bots and Developers

關於細節就不介紹了總之建立好Application以及與頻道用完後時可。

image.png

接著我們先在python上安裝以下package以及ffmpeg.exe。

pip install PyNaCl
pip install yt_dlp
pip install discord

ffmpeg.exe

https://ffmpeg.org/

然後我們實作音樂播放Linked List三個功能:

  • 新增歌
  • 刪除歌
  • 歌單列表
  • 往前播放
  • 往後播放

music.py

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.current = None

    def append(self, song):
        new_node = Node(song)
        if not self.head:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        if not self.current:
            self.current = self.head

    def get_next_song(self):
        if self.current and self.current.next:
            self.current = self.current.next
            return self.current.data
        return None

    def get_previous_song(self):
        current = self.head
        prev = None
        while current:
            if current == self.current:
                self.current = prev
                return prev.data if prev else None
            prev = current
            current = current.next
        return None

    def remove(self, song):
        prev = None
        current = self.head
        while current:
            print(current.data)
            if current.data == song:
                if prev:
                    prev.next = current.next
                else:
                    self.head = current.next
                if current == self.tail:
                    self.tail = prev
                return True
            prev = current
            current = current.next
        return False

    def list_all(self):
        songs = []
        current = self.head
        while current:
            songs.append(current.data)
            current = current.next
        return songs

接著開始設置api_key與建立client

discord_bot.py

import discord

from discord.ext import commands

intents = discord.Intents().all()
client = discord.Client(intents=intents)
bot = commands.Bot(command_prefix='!', intents=intents)

@bot.event
async def on_ready():
    for guild in bot.guilds:
        for channel in guild.text_channels:
            if str(channel) == "general":
                await channel.send('Bot Activated..')
                await channel.send(file=discord.File('add_gif_file_name_here.png'))
        print('Active in {}\n Member Count : {}'.format(guild.name, guild.member_count))

if __name__ == "__main__":
    bot.run("your_api_key")

當擬設置沒問題且執行後就會列出你機器人的channel

image.png

接著要來串接youtube，定義一個class YTDLSource，並將歌單下載下來。

discord_bot.py

import yt_dlp as youtube_dl

youtube_dl.utils.bug_reports_message = lambda: ''

ytdl_format_options = {
    'format': 'bestaudio/best',
    'outtmpl': '%(title)s.%(ext)s',
    'restrictfilenames': True,
    'noplaylist': True,
    'nocheckcertificate': True,
    'ignoreerrors': False,
    'logtostderr': False,
    'quiet': True,
    'no_warnings': True,
    'default_search': 'auto',
    'source_address': '0.0.0.0',  # bind to ipv4
    'fixup': 'warn'  # This flag may help with fixing incomplete files
}
ytdl = youtube_dl.YoutubeDL(ytdl_format_options)

class YTDLSource(discord.PCMVolumeTransformer):
    def __init__(self, source, *, data, volume=0.5):
        super().__init__(source, volume)
        self.data = data
        self.title = data.get('title')
        self.url = ""

    @classmethod
    async def from_url(cls, url, *, loop=None, stream=False):
        loop = loop or asyncio.get_event_loop()
        ytdl.cache.remove()
        data = await loop.run_in_executor(None, lambda: ytdl.extract_info(url, download=not stream))

        if 'entries' in data:
            # take first item from a playlist
            data = data['entries'][0]
        filename = data['title'] if stream else ytdl.prepare_filename(data)
        return filename

到這裡已經建立好discord client以及youtube音樂下載功能，程式碼完整長這樣

discord_bot.py

import asyncio

import discord
import yt_dlp as youtube_dl
from discord.ext import commands

intents = discord.Intents().all()
client = discord.Client(intents=intents)
bot = commands.Bot(command_prefix='!', intents=intents)

ytdl_format_options = {
    'format': 'bestaudio/best',
    'outtmpl': '%(title)s.%(ext)s',
    'restrictfilenames': True,
    'noplaylist': True,
    'nocheckcertificate': True,
    'ignoreerrors': False,
    'logtostderr': False,
    'quiet': True,
    'no_warnings': True,
    'default_search': 'auto',
    'source_address': '0.0.0.0',  # bind to ipv4
    'fixup': 'warn'  # This flag may help with fixing incomplete files
}
ytdl = youtube_dl.YoutubeDL(ytdl_format_options)
youtube_dl.utils.bug_reports_message = lambda: ''

class YTDLSource(discord.PCMVolumeTransformer):
    def __init__(self, source, *, data, volume=0.5):
        super().__init__(source, volume)
        self.data = data
        self.title = data.get('title')
        self.url = ""

    @classmethod
    async def from_url(cls, url, *, loop=None, stream=False):
        loop = loop or asyncio.get_event_loop()
        ytdl.cache.remove()
        data = await loop.run_in_executor(None, lambda: ytdl.extract_info(url, download=not stream))

        if 'entries' in data:
            # take first item from a playlist
            data = data['entries'][0]
        filename = data['title'] if stream else ytdl.prepare_filename(data)
        return filename

@bot.event
async def on_ready():
    for guild in bot.guilds:
        for channel in guild.text_channels:
            if str(channel) == "general":
                await channel.send('Bot Activated..')
                await channel.send(file=discord.File('add_gif_file_name_here.png'))
        print('Active in {}\n Member Count : {}'.format(guild.name, guild.member_count))

if __name__ == "__main__":
    bot.run("your_api_key")

接著來實作discord音樂基本操作功能，這邊要用到discord的command api，實作的功能有

  • 機器人加入聊天室
  • 機器人離開聊天室
  • 新增歌曲
  • 列出所有歌曲
  • 刪除歌曲
  • 音樂撥放
  • 音樂往前播放
  • 音樂往後播放

discord_bot.py

from discord_bot import music_list

ffmpeg_path = "ffmpeg.exe"

@bot.command(name='join_bot', help='Tells the bot to join the voice channel | order: !join_bot')
async def join(ctx):
    if not ctx.message.author.voice:
        await ctx.send("{} is not connected to a voice channel".format(ctx.message.author.name))
        return
    else:
        channel = ctx.message.author.voice.channel
    await channel.connect()

@bot.command(name='leave_bot', help='To make the bot leave the voice channel | order: !leave_bot')
async def leave(ctx):
    voice_client = ctx.message.guild.voice_client
    if voice_client.is_connected():
        await voice_client.disconnect()
    else:
        await ctx.send("The bot is not connected to a voice channel.")

@bot.command(name='insert_music', help='insert music | order: !insert_music {youtube_music_url}')
async def insert_music(ctx, url):
    await ctx.send("正在幫你新增歌曲到歌單中....")
    filename = await YTDLSource.from_url(url, loop=bot.loop)
    music_list.append(filename)
    await ctx.send(f"點歌點好囉\n歌單:\n" + "\n".join(
        [f"第{index + 1}首歌: {song}" for index, song in enumerate(music_list.list_all())]
    ))

@bot.command(name='music_list', help='music list | order: !music_list')
async def list_music(ctx):
    song_list = music_list.list_all()
    if song_list:
        await ctx.send("歌單:\n" + "\n".join([f"第{index + 1}首歌: {song}" for index, song in enumerate(song_list)]))
    else:
        await ctx.send("歌單目前是空的")

@bot.command(name='remove_music', help='remove | order: !remove_music {music_name}')
async def remove_music(ctx, music):
    if music_list.remove(music):
        await ctx.send(f"已移除: {music}")
    else:
        await ctx.send("未找到該歌曲")

@bot.command(name='play_music', help='To play all music Hi Yaku | order: !play_music ')
async def music_li(ctx):
    try:
        server = ctx.message.guild
        voice_channel = server.voice_client
        async with ctx.typing():
            for song in music_list.list_all():
                voice_channel.play(discord.FFmpegPCMAudio(executable=ffmpeg_path, source=song))
                await ctx.send(f'**Now playing:** {song}')

                while voice_channel.is_playing():
                    await asyncio.sleep(2)
    except:
        await ctx.send("The bot is not connected to a voice channel.")

@bot.command(name='next_music', help='Play the next song | order: !next_music')
async def next_music(ctx):
    voice_channel = ctx.message.guild.voice_client
    if voice_channel.is_playing():
        voice_channel.stop()

    if not voice_channel or not voice_channel.is_connected():
        await ctx.send("The bot is not connected to a voice channel.")
        return

    song = music_list.get_next_song()
    if song:
        voice_channel.play(discord.FFmpegPCMAudio(executable=ffmpeg_path, source=song))
        await ctx.send(f"**Now playing next song:** {song}")
    else:
        await ctx.send("No more songs in the queue.")

@bot.command(name='previous_music', help='Play the previous song | order: !previous_music')
async def previous_music(ctx):
    voice_channel = ctx.message.guild.voice_client
    if voice_channel.is_playing():
        voice_channel.stop()
    if not voice_channel or not voice_channel.is_connected():
        await ctx.send("The bot is not connected to a voice channel.")
        return

    song = music_list.get_previous_song()
    if song:
        voice_channel.play(discord.FFmpegPCMAudio(executable=ffmpeg_path, source=song))
        await ctx.send(f"**Now playing previous song:** {song}")
    else:
        await ctx.send("No previous songs in the queue.")

實作完功能後接著就可以開始使用功能

邀請機器人

image.png

查看歌單

image.png

加入音樂

image.png

查看是否加入成功

image.png

播放

image.png

播放中加入新歌單

image.png

完整的程式碼我放在github上，可以自己下載來玩。

GitHub - JED-4a6g0109/discord_bot

結論

List我們平常很常用，因此需要實際了解他的實作方式以及記憶體細節。