概念

鏈表(linked_list)是物理存儲單元上非連續(xù)的颖医、非順序的存儲結(jié)構(gòu)量没，數(shù)據(jù)元素的邏輯順序
是通過鏈表的指針地址實現(xiàn)丑罪，每個元素包含兩個結(jié)點芍耘，一個是存儲元素的數(shù)據(jù)域 (內(nèi)存空間)
，另一個是指向下一個結(jié)點地址的指針域戴涝。根據(jù)指針的指向滋戳，鏈表能形成不同的結(jié)構(gòu)钻蔑，例如
單鏈表，雙向鏈表胧瓜，循環(huán)鏈表等.
鏈表通過將鏈點 i 與其鄰居鏈點 i+1 通過指針相關(guān)聯(lián)，從索引 0 到索引 N-1 對鏈點進
行排序.

實現(xiàn)

class Node:
    """
    鏈點
    """

    def __init__(self, data):
        self.data = data    # 數(shù)據(jù)域
        self.next = None    # 指針域


class SingleLinkedList:
    """
    單鏈表
    """

    def __init__(self, head=None):
        self.head = Node(head)    # 鏈表頭部元素
        self._length = None

    # 向鏈表中添加新鏈點
    def append(self, value):
        self._length = None
        new_node = Node(value)
        # 將頭部節(jié)點指向臨時變量
        current = self.head
        # 當(dāng)頭部節(jié)點存在時
        if self.head:
            # 循環(huán)遍歷到鏈表的最后一個節(jié)點
            while current.next:
                current = current.next
            current.next = new_node
        # 當(dāng)頭部節(jié)點不存在時
        else:
            self.head = new_node

    # 判斷鏈表是否為空
    def is_empty(self):
        return bool(self.head)

    # 向鏈表任意位置插入元素
    def insert(self, position, value):
        self._length = None
        new_node = Node(value)
        # 判斷插入位置是否在鏈表的索引范圍內(nèi)
        if position < 0 or position > self.get_length():
            raise IndexError('Out of linked list range.')

        # 當(dāng)插入位置為頭節(jié)點時
        if position == 0:
            new_node.next, self.head = self.head, new_node
            return
        # 當(dāng)插入位置不在頭節(jié)點時,遍歷鏈表找到插入位置,插入新節(jié)點
        current = self.head
        i = 0
        while i < position:
            pre, current = current, current.next
            i += 1
        pre.next, new_node.next = new_node, current

    # 刪除指定位置的節(jié)點
    def remove(self, position):
        self._length = None
        # 判斷刪除位置是否在鏈表的索引范圍內(nèi)
        if position < 0 or position > self.get_length() - 1:
            raise IndexError('Position out of linked list range.')

        i = 0
        current = self.head
        # 當(dāng)刪除位置為頭節(jié)點時
        if position == i:
            self.head, current.next = self.head.next, None
            return

        # 當(dāng)刪除位置不是頭節(jié)點時,遍歷鏈表找到刪除位置
        i += 1
        prev, current = current, current.next
        while i != position:
            prev, current = current, current.next
            i += 1
        prev.next, current.next = current.next, None

    # 獲取鏈表長度
    def get_length(self):
        if self._length is not None:
            return self._length
        current = self.head
        length = 0
        while current is not None:
            length += 1
            current = current.next
        self._length = length
        return length

    # 遍歷鏈表,并依次打印節(jié)點數(shù)據(jù)
    def print_list(self):
        print('linked_list:')
        current = self.head
        while current is not None:
            print(current.data)
            current = current.next

    # 將鏈表反轉(zhuǎn)
    def reverse(self):
        prev = None
        current = self.head
        while current is not None:
            # next_node = current.next
            # current.next = prev
            # prev = current
            # current = next_node
            next_node, current.next = current.next, prev
            prev, current = current, next_node
        self.head = prev

    # 將列表轉(zhuǎn)換為鏈表
    def init_list(self, data_list):
        self.head = Node(data_list[0])
        current = self.head
        for item in data_list[1:]:
            node = Node(item)
            current.next, current = node, node

    # 替換指定位置的節(jié)點
    def replace(self, position, value):
        # 判斷替換位置是否在鏈表索引范圍內(nèi)
        if position < 0 or position > self.get_length() - 1:
            raise IndexError("Position out of linked-list range.")
        _node = Node(value)
        _current = self.head
        i = 0
        if position == 0:
            _node.next, self.head = self.head.next, _node
            _current.next = None
        else:
            i += 1
            _prev, _current = _current, _current.next
            while i != position:
                i += 1
                _prev, _current = _current, _current.next
            _prev.next, _node.next = _node, _current.next
            _current.next = None

    # 返回給定值的第一個節(jié)點索引
    def index(self, value):
        _current = self.head
        i = 0
        while _current is not None:
            if _current.data == value:
                return i
            i += 1
            _current = _current.next
        return -1

    def __getitem__(self, position):
        if position < 0 or position > self.get_length() - 1:
            raise IndexError("Position out of linked-list range.")
        _current = self.head
        i = 0
        while i != position:
            _current = _current.next
            i += 1
        return _current.data