目錄：資料結構系列文章

單向鏈結串列(Singly Linked List)

用c++實作

#include <iostream>
using namespace std;

template <typename T>
class SinglyLinkedList; // 為了將class SinglyLinkedList設成class ListNode的friend，必須先宣告

template <typename T>
class ListNode
{
public:
    ListNode(T x) : value(x), next(0) {} // 使用c++的成員初始化串列，將value初始化為x，next初始化為0
private:
    T value;
    ListNode<T> *next;
    friend class SinglyLinkedList<T>; // 將class SinglyLinkedList宣告為friend，讓class SinglyLinkedList可以存取ListNode的private成員
};

template <typename T>
class SinglyLinkedList
{
public:
    SinglyLinkedList() : head(0), size(0) {}
    ~SinglyLinkedList()
    {
        ListNode<T> *current = head;
        while (current != 0)
        {
            ListNode<T> *NextNode = current->next;
            delete current;
            current = NextNode;
        }
        head = 0; // 當指標被delete後, 將其指向NULL, 可以避免不必要bug
    }
    void PrintList() // 印出list中的所有資料
    {
        if (head == 0)
        {
            cout << "List is empty." << endl;
        }
        else
        {
            ListNode<T> *current = head;
            while (current != 0) // 節點的traversal(走訪)，從head節點走到最後一個節點
            {
                cout << current->value << " ";
                current = current->next;
            }
            cout << endl;
        }
    }
    void PushFront(T data) // 在list的最前端塞入資料
    {
        ListNode<T> *NewNode = new ListNode<T>(data);
        if (head == 0)
        {
            head = NewNode;
        }
        else
        {
            NewNode->next = head;
            head = NewNode;
        }
        ++size;
    }
    void PopFront() // 移除list中的第一個資料
    {
        if (head == 0)
        {
            cout << "List is empty." << endl;
        }
        else
        {
            ListNode<T> *NextNode = head->next;
            delete head;
            head = NextNode;
        }
        --size;
    }
    void PushBack(T data) // 在list的最後端塞入資料
    {
        if (head == 0)
        {
            PushFront(data);
        }
        else
        {
            ListNode<T> *NewNode = new ListNode<T>(data);
            ListNode<T> *current = head;
            while (current->next != 0)
            {
                current = current->next;
            }
            current->next = NewNode;
            ++size;
        }
    }
    void PopBack() // 移除list中的最後一個資料
    {
        if (head == 0)
        {
            cout << "List is empty." << endl;
        }
        else
        {
            ListNode<T> *current = head;
            while (current->next->next != 0)
            {
                current = current->next;
            }
            delete current->next;
            current->next = 0; // 這邊因為是最後一個節點，所以delete掉後一定要把它指向NULL，不然PrintList中會產生無窮迴圈
            --size;
        }
    }
    void DeleteData(T data) // 刪除list中的T data資料
    {
        ListNode<T> *previous = 0, *current = head;
        while (current != 0 && current->value != data) // 如果current為null或current的資料為我們所要刪除的就停止traversal
        {
            previous = current;
            current = current->next;
        }
        if (current == 0) // current為null代表list為空或是list中不存在我們想要刪除的資料
        {
            cout << "There is no " << data << " in list." << endl;
        }
        else if (current == head) // 如果我們想要刪除的資料是第一個節點
        {
            head = current->next;
            delete current;
            current = 0;
            --size;
        }
        else // 想要刪除的資料不是第一個節點
        {
            previous->next = current->next;
            delete current;
            current = 0;
            --size;
        }
    }
    void Clear() // 清除list中所有資料
    {
        int i = 0;
        while (head != 0)
        {
            ListNode<T> *current = head;
            head = head->next;
            delete current;
            current = 0;
        }
        size = 0;
    }
    void Reverse() // 把整串list反轉
    {
        if (head != 0 && head->next != 0) // 如果list為空或是只有1個節點，那就不須做任何動作
        {
            ListNode<T> *previous = 0, *current = head;
            while (current != 0) // 從最前面的Null節點traversal到最後一個節點
            {
                ListNode<T> *NextNode = current->next; // 用變數紀錄原本的下一個節點
                current->next = previous;              // 把節點反過來指
                previous = current;
                current = NextNode;
            }
            head = previous;
        }
    }
    int getSize() // 回傳list資料個數
    {
        return size;
    }
    T getHead() // 回傳第一個資料
    {
        if (isEmpty())
        {
            cout << "List is empty." << endl;
            return 0;
        }
        else
        {
            return head->value;
        }
    }
    bool isEmpty() // 回傳list是否為空
    {
        return head == 0;
    }

private:
    ListNode<T> *head;
    int size;
};
int main()
{
    SinglyLinkedList<double> list;
    list.PrintList();
    cout << list.isEmpty() << endl;
    cout << list.getSize() << endl;
    cout << list.getHead() << endl;
    list.DeleteData(4);
    list.PushBack(1);
    cout << list.getSize() << endl;
    list.PushBack(3);
    list.PushFront(5);
    list.PushFront(7);
    list.PrintList();
    cout << list.isEmpty() << endl;
    cout << list.getSize() << endl;
    cout << list.getHead() << endl;
    list.PopBack();
    list.PushBack(9);
    list.DeleteData(5);
    list.PrintList();
    list.PushFront(11);
    list.PushFront(16);
    list.PushBack(13);
    list.PrintList();
    list.PopFront();
    list.PushBack(15);
    list.DeleteData(1);
    list.PrintList();
    list.Reverse();
    list.PrintList();
    cout << list.isEmpty() << endl;
    cout << list.getSize() << endl;
    cout << list.getHead() << endl;
    list.Clear();
    list.PrintList();
    cout << list.getHead();
    return 0;
}

output:

List is empty.
1
0
List is empty.
0
There is no 4 in list.
1
7 5 1 3 
0
4
7
7 1 9 
16 11 7 1 9 13 
11 7 9 13 15 
15 13 9 7 11 
0
5
15
List is empty.
List is empty.
0

用python實作

class ListNode:
    def __init__(self, x):
        self.value = x
        self.next = None


class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def PrintList(self): # 印出list中的所有資料
        if self.head is None:
            print("List is empty.")
        else:
            current = self.head
            while current is not None: # 節點的traversal(遍歷或尋訪)，從head節點走到最後一個節點
                print(current.value, end=' ')
                current = current.next
            print()

    def PushFront(self, data): # 在list的最前端塞入資料
        NewNode = ListNode(data)
        if self.head is None:
            self.head = NewNode
        else:
            NewNode.next = self.head
            self.head = NewNode
        self.size += 1

    def PopFront(self): # 移除list中的第一個資料
        TempNode = self.head
        if TempNode is None:
            print("List is empty.")
        else:
            self.head = TempNode.next
            TempNode = None
        self.size -= 1

    def PushBack(self, data): # 在list的最後端塞入資料
        if self.head is None:
            self.PushFront(data)
        else:
            TempNode = self.head
            while(TempNode.next is not None):
                TempNode = TempNode.next
            TempNode.next = ListNode(data)
            self.size += 1
        

    def PopBack(self): # 移除list中的最後一個資料
        TempNode = self.head
        if TempNode is None:
            print("List is empty.")
        else:
            while(TempNode.next.next is not None):
                TempNode = TempNode.next
            TempNode.next = None
        self.size -= 1

    def DeleteData(self, data): # 刪除list中的T data資料
        previous = None
        current = self.head
        while (current is not None and current.value != data): # 如果current為null或current的資料為我們所要刪除的就停止traversal
            previous = current
            current = current.next
        if current is None: # current為null代表list為空或是list中不存在我們想要刪除的資料
            print("There is no " + str(data) + " in list")
        elif current == self.head: # 如果我們想要刪除的資料是第一個節點
            self.head = current.next
            current = None
            self.size -= 1
        else: # 想要刪除的資料不是第一個節點
            previous.next = current.next
            current = 0
            self.size -= 1

    def Clear(self): # 清除list中所有資料
        while self.head is not None:
            current = self.head
            self.head = current.next
            current = 0
        self.size = 0

    def Reverse(self): # 把整串list反轉
        if self.head is not None and self.head.next is not None: #  如果list為空或是只有1個節點，那就不須做任何動作
            previous = None
            current = self.head
            while current: # 從最前面的Null節點traversal到最後一個節點
                NextNode = current.next #  用變數紀錄原本的下一個節點
                current.next = previous #  把節點反過來指
                previous = current
                current = NextNode
            self.head = previous

    def GetSize(self): # 回傳list資料個數
        return self.size

    def isEmpty(self): # 回傳list是否為空
        return self.head is None


def main():
    list = SinglyLinkedList()
    list.PrintList()
    print(list.isEmpty())
    print(list.GetSize())
    list.DeleteData(4)
    list.PushBack(1)
    print(list.GetSize())
    list.PushBack(3)
    list.PushFront(5)
    list.PushFront(7)
    list.PrintList()
    print(list.isEmpty())
    print(list.GetSize())
    list.PopBack()
    list.PushBack(9)
    list.DeleteData(5)
    list.PrintList()
    list.PushFront(11)
    list.PushFront(16)
    list.PushBack(13)
    list.PrintList()
    list.PopFront()
    list.PushBack(15)
    list.DeleteData(1)
    list.PrintList()
    list.Reverse()
    list.PrintList()
    print(list.isEmpty())
    print(list.GetSize())
    list.Clear()
    list.PrintList()


if __name__ == '__main__': # 檔案被import時，不執行main()函式
    main()

output:

List is empty.
1
0
There is no 4 in list.
1
7 5 1 3 
0
4
7 1 9 
16 11 7 1 9 13 
11 7 9 13 15 
15 13 9 7 11 
0
5
List is empty.

下一篇：資料結構 堆疊(Stack)