C++和python如何實(shí)現(xiàn)單鏈表

這篇文章給大家分享的是有關(guān)C++和python如何實(shí)現(xiàn)單鏈表的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

一、鏈表的基本概念

鏈表是數(shù)據(jù)元素的線性集合（Linear Collection），物理存儲不連續(xù)。那么，這種設(shè)計的優(yōu)點(diǎn)是什么？缺點(diǎn)又是什么？

鏈表的基本結(jié)構(gòu)：

鏈表是由一系列的“節(jié)點(diǎn)”組成在一起的集合，節(jié)點(diǎn)（Node）由數(shù)據(jù)域（data）和指針域（next）組成。

從功能上看，data負(fù)責(zé)存儲數(shù)據(jù)，next負(fù)責(zé)存儲下一個節(jié)點(diǎn)的位置。當(dāng)然，用更加嚴(yán)格的語句來講，next存儲的是其直接后繼的地址，關(guān)于直接后繼的定義見：

鏈表的分類：

常見的鏈表種類有：單向鏈表、雙向鏈表、單向循環(huán)鏈表、雙向循環(huán)鏈表，將會在后面文章中單獨(dú)介紹各種鏈表的結(jié)構(gòu)和代碼實(shí)現(xiàn)，以及對應(yīng)的鏈表操作。

鏈表的基本操作：

鏈表的基礎(chǔ)操作包含：插入、刪除、查找、合并等，此外還有：反轉(zhuǎn)、排序、深度復(fù)制等。

鏈表的優(yōu)點(diǎn)：

• 插入和刪除快；

• 存儲空間不受限制，可動態(tài)申請擴(kuò)充，不需事先開辟內(nèi)存；

鏈表的缺點(diǎn)：

• 相比于數(shù)組，鏈表的需要更多的存儲空間（需存儲指針）；

• 存儲不連續(xù)導(dǎo)致其訪問時間長；

• 從反向訪問角度，單向鏈表難以反向訪問，擴(kuò)展為雙向鏈表則需要額外存儲反向指針；

• 每次節(jié)點(diǎn)訪問都需要從頭部開始；

二、單鏈表

基本結(jié)構(gòu)：

單鏈表的結(jié)構(gòu)含有四個概念：頭指針、頭結(jié)點(diǎn)、普通Node、尾結(jié)點(diǎn)，下面分別介紹：

• 頭指針指向頭結(jié)點(diǎn)，是單鏈表的表示，必不可少；

• 頭結(jié)點(diǎn)是單鏈表的第一個節(jié)點(diǎn)，其數(shù)據(jù)域內(nèi)容一般無效；

• 普通Node即用于數(shù)據(jù)存儲和直接后繼指針存儲的節(jié)點(diǎn)；

• 尾結(jié)點(diǎn)即鏈表中最后一個節(jié)點(diǎn)，其指針域next為空，其后無節(jié)點(diǎn)；

單鏈表的基本操作：

針對單鏈表常見的操作有：增、改、查、刪等，

常用的操作如下：

（1）增

對鏈表添加元素一般有三種方法：頭插法(add)、尾插法(append)、任意位置插入法(insert)。

（2）改

改動鏈表中某個節(jié)點(diǎn)的data。

（3）查

查找分為按值查找和按位置查找兩種，前者表示按照值查找對應(yīng)位置，后者表示按位置查找對應(yīng)值；

（4）刪

刪除分為按值刪除和按位置刪除兩種；前者表示按照值刪除對應(yīng)節(jié)點(diǎn)，后者表示按照位置刪除對應(yīng)節(jié)點(diǎn)；

實(shí)現(xiàn)說明：

按照自己目前所看的資料，一般都會實(shí)現(xiàn)下面介紹的這些函數(shù)，具體介紹放在python和C++實(shí)現(xiàn)中。

1.python實(shí)現(xiàn)

（1）節(jié)點(diǎn)設(shè)計

按照單鏈表的定義可知，節(jié)點(diǎn)包含數(shù)據(jù)域data和指針域next：

但是由于next和python的內(nèi)置函數(shù)next()重名，所以指針域使用pointer表示。

代碼如下：

class Node:
    def __init__(self, data):
        """
        Args:
            data: data of node, any type 
        """
        self.data = data
        self.pointer = None

（2）鏈表類：Single_Linked_List

上述Node類對象即為鏈表的基本組成結(jié)構(gòu)，可以用于實(shí)現(xiàn)頭結(jié)點(diǎn)、普通節(jié)點(diǎn)和尾結(jié)點(diǎn)。

因此，鏈表類只需要提供頭指針：

class Single_Linked_List:
    def __init__(self, node=None):
        self.__head = node

（3）判斷鏈表是否為空：is_empty()函數(shù)

實(shí)際上，只需要判斷頭指針是否指向Node類對象（或是否等于None），就可判斷一個鏈表是否為空：

def is_empty(self):
    """判斷鏈表是否為空"""
    if self.__head == None:
        return True
    else:
        return False

（4）頭插法：add()函數(shù)

在鏈表頭進(jìn)行節(jié)點(diǎn)插入是很常見的插入操作，這種方式使得“先插入的節(jié)點(diǎn)在鏈表尾部”。頭插法需要將頭指針指向新的節(jié)點(diǎn)，并讓新的節(jié)點(diǎn)指向原來的頭結(jié)點(diǎn)：

def add(self, data):
    """Add dnode into head
    """ 
    # 創(chuàng)建新節(jié)點(diǎn)
    node = Node(data)
    # 令新的節(jié)點(diǎn)指向原來的頭結(jié)點(diǎn)
    node.pointer = self.__head
    # 令頭指針指向新的節(jié)點(diǎn)
    self.__head = node

（5）尾插法：append()函數(shù)

如果想要鏈表節(jié)點(diǎn)次序和插入次序相同，就需要使用尾插法。在插入之前需要判斷鏈表是否為空，如果不為空才能進(jìn)行插入（可以調(diào)用前面定義的is_empty()函數(shù)，但是下述代碼沒有）。

此外，還需要進(jìn)行鏈表的遍歷操作，找到最后一個節(jié)點(diǎn)。單鏈表只能從表頭開始訪問，所以每次尾插都必須遍歷。

def append(self, data):
    """ append node into tail
    """
    node = Node(data)
    
    # 頭指針為空時即為首節(jié)點(diǎn)
    if self.__head == None:
        self.__head = node
    # 頭指針不為空時進(jìn)行遍歷
    else:
        current = self.__head
        while current.pointer != None:
            current = current.pointer
        current.pointer = node

（6）在任意位置插入：insert()函數(shù)

前面介紹的頭插法和尾插法，其原理相對簡單，但是并不能完全滿足插入需求。如果知道目標(biāo)插入的位置，可以采用insert()函數(shù)實(shí)現(xiàn)任意位置的節(jié)點(diǎn)插入。

需要注意的是，在實(shí)現(xiàn)insert()函數(shù)時必須考慮到“position”參數(shù)可能出現(xiàn)的幾種情況。比如python中并沒有明確的類型要求，所以要檢查“position”是不是int類型。

對于核心的節(jié)點(diǎn)插入實(shí)現(xiàn)功能，需要找到目標(biāo)插入位置對應(yīng)的節(jié)點(diǎn)，并使得這個節(jié)點(diǎn)指向新節(jié)點(diǎn)，讓新節(jié)點(diǎn)指向原位置節(jié)點(diǎn)的后一個節(jié)點(diǎn)。這個過程類似于鐵鏈中加入鐵環(huán)的過程，要保證新鐵環(huán)和原來的兩個鐵環(huán)相連接。

def insert(self, position, data):
    """在任意位置插入節(jié)點(diǎn)
    Args:
        position:插入節(jié)點(diǎn)的位置,int
        data:插入節(jié)點(diǎn)的值
    """
    
    if not isinstance(position, int):
        raise ValueError("expect type is 'int', but got {}".format(position.__class__))
    
    # 頭插法
    if position <= 0:
        self.add(data)
    # 尾插法
    elif position > self.get_length():
        self.append(data)
    
    else:
        current = self.__head
        current_position = 0
        node = Node(data)
        # 目的：計算出插入位置
        while current_position < position -1:
            current_position += 1
            current = current.pointer
        # 首先：必須使得當(dāng)前節(jié)點(diǎn)的pointer指針指向新建的node
        # 其次：必須保證新建的node的pointer指向當(dāng)前節(jié)點(diǎn)的后一個節(jié)點(diǎn)
        node.pointer = current.pointer
        current.pointer = node

（7）計算鏈表長度：get_length()函數(shù)

對于調(diào)用者和類內(nèi)部的其它函數(shù)來做，鏈表長度是一個非常有用的值。比如在插入函數(shù)insert()中，需要判斷插入位置是不是大于鏈表長度。

計算鏈表長度的實(shí)現(xiàn)比較簡單，只需要遍歷鏈表的所有節(jié)點(diǎn)，并用計數(shù)器來統(tǒng)計節(jié)點(diǎn)的數(shù)目即可。

def get_length(self):
    """ 獲取鏈表的長度"""
    # 沒有任何node
    if self.__head == None:
        return 0
    # 節(jié)點(diǎn)數(shù)統(tǒng)計
    else:
        current = self.__head
        length = 0
        while current != None:
            current = current.pointer
            length += 1
        return length

（8）遍歷所有節(jié)點(diǎn)：traversal()函數(shù)

鏈表、樹、圖等結(jié)構(gòu)都需要遍歷操作，其中鏈表的遍歷比較簡單，只需要依次的訪問所有節(jié)點(diǎn)即可。

def traversal(self):
    current = self.__head
    i = 0
    # 循環(huán)結(jié)束的條件依舊是節(jié)點(diǎn)的pointer指向不為空
    while current !=  None:
        print("Element {} is {} ".format(i, current.data))
        current = current.pointer
        i += 1

（9）搜索：search()函數(shù)

前面提到搜索有按值搜索和按位置搜索兩種，它們的原理和實(shí)現(xiàn)都十分相似，所以僅以按值搜索為例。

需要注意的是，insert()函數(shù)需要判斷鏈表是否為空，并且需要考慮到目標(biāo)值不在鏈表中的情況，分別對應(yīng)不同的返回值。

def search(self, data):
    """ 返回值為data的第一個節(jié)點(diǎn)"""
    if self.__head == None:
        return -1
    else:
        current = self.__head
        current_position = 0
        # 遍歷節(jié)點(diǎn)
        while current != None:
            # 目標(biāo)值搜索成功
            if current.data == data:
                return current_position
            # 目標(biāo)值搜索不到則繼續(xù)搜索       
            else:
                current_position += 1
                current = current.pointer
    # 目標(biāo)值不存在于鏈表中         
    return False

（10）刪除：delete()函數(shù)

上述的查找中以“按值查找”為例，這次刪除中同樣以“按值刪除”為例，“按位置刪除”的實(shí)現(xiàn)與之類似。

按值刪除，即刪除目標(biāo)值對應(yīng)的目標(biāo)節(jié)點(diǎn)。在進(jìn)行遍歷時，需要記錄當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的前一個節(jié)點(diǎn)。因?yàn)?，一旦查找大目?biāo)值所在的目標(biāo)節(jié)點(diǎn)，需要令目標(biāo)節(jié)點(diǎn)的前一個節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)的下一個節(jié)點(diǎn)，即完成節(jié)點(diǎn)的刪除。

def delete(self, data):
    """ 刪除值為data的第一個節(jié)點(diǎn)"""
    if self.is_empty():
        return None
    
    # 記錄當(dāng)前節(jié)點(diǎn)和前一個節(jié)點(diǎn)
    current = self.__head
    piror = None
    while current != None:
        # 查找成功分為兩種情況
        if current.data == data:
            # 目標(biāo)節(jié)點(diǎn)為頭結(jié)點(diǎn)
            if current == self.__head:
                self.__head = self.__head.pointer
                return True
             # 目標(biāo)節(jié)點(diǎn)不是頭結(jié)點(diǎn)
             # 令目標(biāo)節(jié)點(diǎn)的前一個節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)的后一個節(jié)點(diǎn)   
            else:
                piror.pointer = current.pointer
                return True
         # 更新當(dāng)前節(jié)點(diǎn)和前一個節(jié)點(diǎn)
         else:
            piror = current
            current = current.pointer
    return False

2.C++實(shí)現(xiàn)

前面的python實(shí)現(xiàn)中已經(jīng)分析了各個函數(shù)的作用，以及對應(yīng)的實(shí)現(xiàn)過程。雖然python和C++的語法不同，但是核心過程是類似的，所以下面不再重復(fù)對過程的敘述。

（1）節(jié)點(diǎn)設(shè)計

由于C++的指針必須指定類型，所以需要使用空指針NULL作為pointer的值。

class Node{
public:
    int data;
    Node *pointer=NULL;
};

（2）鏈表類：SingleLinkedList

遵循聲明和實(shí)現(xiàn)分類的策略，先對各個函數(shù)進(jìn)行聲明。

class SingleLinkedList {
public:
    SingleLinkedList();
    bool isEmpty();
    int getLength();
    void add(int data);
    void append(int data);
    void insert(int position, int data);
    void traversal();
    int search(int data);
    void remove(int data);

private:
    Node *head;
};

（3）判斷鏈表是否為空：isEmpty()函數(shù)

bool SingleLinkedList::isEmpty() {
    // 頭結(jié)點(diǎn)不指向任何結(jié)點(diǎn)，為空
    if (head->pointer == NULL) {
        return true;
    }
    else {
        return false;
    }
}

（4）頭插法：add()函數(shù)

void SingleLinkedList::add(int data) {
    // 當(dāng)原列表僅有頭結(jié)點(diǎn)時，直接插入新節(jié)點(diǎn)即可
    if (head->pointer == NULL) {
        head->pointer = new Node;
        head->pointer->data = data;
        
    }
    // 當(dāng)原列表頭結(jié)點(diǎn)后面含有后繼節(jié)點(diǎn)時
    // 令頭結(jié)點(diǎn)直接后繼為新節(jié)點(diǎn)
    // 并令新節(jié)點(diǎn)的直接后繼為原來頭結(jié)點(diǎn)的直接后繼
    else {
        // 臨時存儲頭結(jié)點(diǎn)的直接后繼
        Node *temp = head->pointer;
        head->pointer = new Node;
        head->pointer->data = data;
        head->pointer->pointer = temp;
    }
}

（5）尾插法：append()函數(shù)

void SingleLinkedList::append(int data) {
    Node *current = head->pointer;
    // 找到列表的最后一個節(jié)點(diǎn)的位置current
    // current的指針域?yàn)镹ULL
    while (current->pointer!=NULL)
    {
        current = current->pointer;
    }
    // 令current的指針域指向新節(jié)點(diǎn)，完成插入
    current->pointer = new Node;
    current->pointer->data = data;
}

（6）在任意位置插入：insert()函數(shù)

void SingleLinkedList::insert(int position, int data) {
    // 頭插法
    if (position <= 0) {
        add(data);
    }
    // 尾插法
    else if (position > getLength()){
        append(data);
    }
    else {
        // 令頭指針?biāo)诘奈恢脼?
        int current_position = 0;
        Node *current = head;
        Node *prior = NULL;
        // 查找目標(biāo)節(jié)點(diǎn)位置current，并記錄其直接前驅(qū)節(jié)點(diǎn)piror
        while (current_position<position)
        {
            // 更新當(dāng)前節(jié)點(diǎn)和直接前驅(qū)
            prior = current;
            current = current->pointer;
            current_position++;
        }
        // 目標(biāo)位置的直接前驅(qū)prior指向新節(jié)點(diǎn)
        // 新節(jié)點(diǎn)指向目標(biāo)位置的節(jié)點(diǎn)
        prior->pointer = new Node;
        prior->pointer->data = data;
        prior->pointer->pointer = current;
    }
};

（7）計算鏈表長度：getLength()函數(shù)

int SingleLinkedList::getLength() {
    int counter = 0;
    Node *current = head;
    // 遍歷鏈表，直到最后一個元素
    while (current->pointer!=NULL)
    {
        counter++;
        current = current->pointer;
    }
    return counter;
}

（8）遍歷所有節(jié)點(diǎn)：traversal()函數(shù)

void SingleLinkedList::traversal() {
    Node *current;
    // 指向頭結(jié)點(diǎn)的直接后繼
    current = head->pointer;
    int counter = 1;
    // 遍歷鏈表，輸出每個節(jié)點(diǎn)的值
    while (current!=NULL)
    {
        printf("Element in %d is %d \n", counter, current->data);
        counter++;
        current = current->pointer;
    }
}

（9）搜索：search()函數(shù)

int SingleLinkedList::search(int data) {
    int current_position = 1;
    Node *current = head->pointer;
    while (current!=NULL)
    {
        // 搜索成功返回當(dāng)前位置
        if (current->data == data) {
            return current_position;
        }
        // 繼續(xù)更新位置；
        current = current->pointer;
        current_position++;
    }
    // 搜索失敗，返回-1
    return -1;
}

（10）刪除：remove()函數(shù)

void SingleLinkedList::remove(int data) {
    Node *current = head->pointer;
    Node *prior = head;
    // 遍歷鏈表
    while (current!=NULL)
    {
        // 查找到目標(biāo)位置
        if (current->data == data) {
            // 令目標(biāo)位置的直接前驅(qū)指向目標(biāo)節(jié)點(diǎn)的直接后繼
            prior->pointer = current->pointer;
            break;
        }
        // 更新當(dāng)前節(jié)點(diǎn)和其前驅(qū)節(jié)點(diǎn)
        prior = current;
        current = current->pointer;
    }
}

感謝各位的閱讀！關(guān)于“C++和python如何實(shí)現(xiàn)單鏈表”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！