概念圖

image.png

• 單鏈表是由一些具體的結(jié)點(diǎn)組成
• 每個(gè)結(jié)點(diǎn)都是一個(gè)對(duì)象，有直自己的標(biāo)識(shí)
• 結(jié)點(diǎn)之間通過指針單項(xiàng)鏈接而成

表示鏈表結(jié)束，用結(jié)點(diǎn)的指針域指向空

表頭添加數(shù)據(jù)

首先將新結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)，在將頭指針指向新結(jié)點(diǎn)

image.png

一般情況添加數(shù)據(jù)

將新結(jié)點(diǎn)指針區(qū)域指向當(dāng)前結(jié)點(diǎn)的next區(qū)域，將當(dāng)前結(jié)點(diǎn)的next區(qū)域指向新節(jié)點(diǎn)

image.png

刪除結(jié)點(diǎn)

image.png

python實(shí)現(xiàn)單鏈表

單鏈表結(jié)點(diǎn)構(gòu)造

class Node:
    """
    單鏈表結(jié)點(diǎn)
    """
    def __init__(self, value):
        self.data = value
        self.next = None

單鏈表具體實(shí)現(xiàn)

class SingleLinkList:
    def __init__(self):
        self.__head = None

    def is_empty(self):
        """
        判斷鏈表是否為空
        :return:
        """
        return self.__head is None

    def length(self):
        """計(jì)算鏈表的長(zhǎng)度"""
        cur = self.__head
        i = 0
        while cur is not None:
            cur = cur.next
            i += 1
        return i

    def append(self, value):
        """在鏈表尾部添加"""
        node = Node(value)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next is not None:
                cur = cur.next
            cur.next = node

    def add(self, value):
        """在鏈表頭部添加數(shù)據(jù)"""
        node = Node(value)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            node.next = cur
            self.__head = node

    def insert(self, index, value):
        """指定位置插入數(shù)據(jù)"""
        node = Node(value)
        cur = self.__head
        if index <= 0 or cur is None:
            self.add(value)
        elif index > self.length() - 1:
            self.append(value)
        else:
            count = 0
            while cur.next is not None and count < index - 1:
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    def pop(self, index=0):
        """指定位置刪除，默認(rèn)刪除第一個(gè)元素"""
        if not self.is_empty():
            if index == 0:
                cur = self.__head
                self.__head = cur.next
                return cur.data
            else:
                cur = self.__head
                pre = None
                count = 0
                if index > self.length()-1:
                    raise IndexError("索引超出范圍")
                while cur.next is not None and count != index:
                    count += 1
                    pre = cur
                    cur = cur.next
                pre.next = cur.next
                return cur.data

    def remove(self, value):
        """指定數(shù)據(jù)第一個(gè)刪除"""
        cur = self.__head
        pre = None
        while cur is not None:
            if cur.data == value:
                if not pre:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

    def search(self, value):
        """查詢數(shù)據(jù)是否在鏈表中，返回第一個(gè)數(shù)據(jù)的索引， 沒有則返回 -1"""
        if self.is_empty():
            return -1
        else:
            cur = self.__head
            count = 0
            while cur is not None:
                if cur.data == value:
                    return count
                count += 1
                cur = cur.next
            return -1

    def __repr__(self):
        data = []
        cur = self.__head
        while cur is not None:
            data.append(str(cur.data))
            cur = cur.next
        return "->".join(data)


if __name__ == '__main__':
    link_list = SingleLinkList()
    link_list.append(10)
    link_list.append(1)
    link_list.append(0)
    link_list.add(2)
    link_list.insert(2, 16)
    print(link_list.length())
    print(link_list)
    print(link_list.search(3))