资料结构 链结串列(Linked List)

目录：资料结构系列文章

单向链结串列(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初始化为0private:    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.10List is empty.0There is no 4 in list.17 5 1 3 0477 1 9 16 11 7 1 9 13 11 7 9 13 15 15 13 9 7 11 0515List is empty.List is empty.0

用python实作

class ListNode:    def __init__(self, x):        self.value = x        self.next = Noneclass 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 Nonedef 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.10There is no 4 in list.17 5 1 3 047 1 9 16 11 7 1 9 13 11 7 9 13 15 15 13 9 7 11 05List is empty.

下一篇：资料结构 堆叠(Stack)