Единый список

В этом блоге мы представляемЕдиный списокЭта структура данных, структура связанного списка, представляет собой альтернативу последовательностям на основе массивов (таким как списки Python).

Последовательности на основе массива также имеют следующие недостатки:

1. Динамический массив может быть длиннее, чем необходимо для фактического хранения элементов массива.
2. Амортизированные ограничения на операции неприемлемы в системах реального времени.
3. Вставка и удаление операций внутри массива слишком затратны

И последовательности на основе массивов, и связанные списки сохраняют в себе определенный порядок элементов, но совершенно по-разному.

• Массив — это блок памяти, который может обеспечивать хранение и ссылки на множество элементов.
• Связанный список использует более децентрализованную структуру, называемуюузелОблегченный объект, назначенный каждому элементу. Каждый узел поддерживает ссылку на свои элементы и содержит одну или несколько ссылок на соседние узлы.

цепная структура

Что такое цепное хранение линейной таблицы, то есть для хранения элементов линейной таблицы используется группа произвольных единиц хранения, причем эта группа элементов хранения может быть непрерывной или прерывистой. Конечно, мы понимаем непрерывное, но что, если оно не является непрерывным? Его можно соединить цепочкой, что такое цепочка? Самое интуитивное ощущение следующее:

Мы знаем, что в языке C есть указатели, и указатель находит свою цель по адресу. Таким образом, узел не только имеет свой элемент, но также должен иметь адрес своего следующего элемента. Структура хранения, состоящая из этих двух частей, называется узлом, то есть узел содержит два поля: поле данных и поле указателя Структурная схема структуры выглядит следующим образом:

Ссылки в Python

Итак, здесь нужны указатели и адреса.Мы не слышали, что в Python есть указатели в C или C++, когда изучали основы.Что такое указатели в Python? Давайте сначала отложим эту концепцию в сторону.Когда дело доходит до указателей, люди, которые плохо знакомы с C и C++, могут бояться (и я тоже боюсь), поэтому давайте сначала разберемся в природе переменных в Python.

>>> a = 100
>>> b = 100
>>> id(a)
4343720720
>>> id(b)
4343720720
>>>
>>> a, b = 10, 20
>>> id(a)
4343717840
>>> id(b)
4343718160
>>> a, b = b, a
>>> id(a)
4343718160
>>> id(b)
4343717840
>>>

1. при объявленииa = 100а такжеb = 100, ты можешь найтиid(a) == id(b), почему значения id у a и b совпадают? Давайте посмотрим на эту картинку:

Мы используем приведенную выше картинку, чтобы сделать метафору, которая может быть не очень точной, но удобной для понимания. Если компьютер рассматривается как здание, то пространство памяти эквивалентно каждой комнате в здании, адрес памяти - это номер дома этой комнаты, и данные (такие как номер 100, номер 10 или другие типы) могут быть сохранены в этой комнате.

Если однажды есть маленький а, который хочет снять дом, и маленький а говорит: «Мне нравится эта комната с номером дома (адрес памяти 4343720720)», и уверенно снимает эту комнату, поэтому а = 100. Сяо жил в этой комнате, когда мы спросилиid(a)Когда компьютер возвращает нам номер дома этой комнаты (то есть адрес памяти 4343720720). Точно так же Сяо Б тоже полюбил этот дом и жил в нем с уверенностью. И поскольку все данные, хранящиеся в комнате, равны 100, несмотря на то, что a и b имеют разные имена, они находятся в одной комнате, поэтому адрес памяти одинаков.

2. при объявленииa = 10а такжеb = 20, ситуация изменилась, и этот процесс на самом деле легко понять, он эквивалентен тому, что маленький a и маленький b смотрят на разные комнаты (маленький a смотрит на комнату с номером дома 4343717840, маленький b глядя на номер дома № 4343718160), когда они заселились, в этой комнате хранились разные данные (a=10, b=20). когда они обмениваютсяa, b = b, a, что эквивалентно обмену комнатами, но данные в комнате не изменились. наконецa=20, b =10, потому что число, хранящееся по адресу памяти 4343717840, равно 10, а число, хранящееся по адресу 4343718160, равно 20.

Изначально я собирался ввести односвязный список, зачем говорить о ссылках в Python? Поскольку структура данных односвязного списка, который мы собираемся представить, будет использоватьссылка на объектэто понятие. Сами переменные хранят адрес, и замена их значений — это изменение собственных указателей. В Python нет указателей, поэтому в реальном программировании вместо этого обычно используются ссылки. Введение в ссылки на Python здесь не очень подробное.Если читатели все еще не понимают, они могут узнать больше из других материалов.

Определение узла и реализация кода Python

Узел, используемый для построения части односвязного списка, имеет два члена: член элемента и член поля указателя.

Член элемента: относится к произвольному объекту, который является элементом последовательности a1, a2, ..., an на следующем рисунке.

Член поля указателя: указывает на последующий узел односвязного списка или нуль, если узла-преемника нет.

Познакомившись со структурой цепочки, мы можем очень хорошо написать код Python для узла.

class Node(object):
    """声明节点"""

    def __init__(self, element):
        self.element = element  # 给定一个元素
        self.next = None  # 初始设置下一节点为空

Итак, что такое односвязный список

Единый списокВ простейшей форме набор узлов вместе образует линейную последовательность. Каждый узел хранит ссылку на объект, указывающий на элемент в последовательности, которая хранит следующий узел в списке.

Односвязный список — это цепочка структур данных доступа, в которой используется произвольный набор адресов.единица храненияхранится в линейной таблицеэлемент данных. Данные в связанном списке представлены узлами, и состав каждого узла: элемент (элемент данныхизображение) +указатель(с указанием места хранения последующих элементов), элемент — это единица хранения для хранения данных, а указатель — адрес данных, соединяющий каждый узел.

На самом деле вышеперечисленные термины объясняются на просторечии жизни, то есть нас теперь трое — я, ты и он. Когда я указываю пальцем на вас (примечание: поскольку это односвязный список, вы не можете указывать на меня), вы указываете пальцем на него, формируя, таким образом, односвязный список. Палец — это ссылка, а «я, ты, он» — элемент последовательности. Метод "я->ты->он" представляет собой простой односвязный список, интересно, вы его понимаете?

• Головной узел: первый узел связанного списка.

• хвостовой узел: последний узел связанного списка

  Начиная с головного узла, можно переходить от узла к узлу через «следующую» ссылку каждого узла, в конечном итоге достигая хвостового узла списка.

  Если ссылка **"next"** текущего узла указывает на ноль, мы можем определить, что узел является хвостовым узлом. Этот процесс обычно называют遍历链表.

Какие операции выполняет односвязный список?

Работа со связанным списком несложна, если вы понимаете структуру узла: элемент поля данных и поле указателя рядом. И различные операции на самом деле являются операциями над указателями, будь то добавление, удаление, изменение или проверка, все из которых заключаются в том, чтобы сначала найти указатель, а затем получить элемент. Каковы конкретные основные операции, которые я выполнил? Как следует (конечно, есть еще операции, о которых я, возможно, не подумал, надеюсь, вы сможете привести их в комментариях.)

увеличивать

• пробка для головы
• вставка хвоста
• Вставить элемент в указанную позицию

удалять

• удалить головной узел
• удалить хвостовой узел
• удалить указанный элемент

изменять

• Изменить элемент в указанной позиции

чек об оплате

• Пройтись по всему односвязному списку

• Запрос, существует ли указанный элемент

другие операции

• Пустой связанный список
• Найдите длину связанного списка
• Перевернуть весь связанный список (опросить высокочастотные тестовые сайты)

Python реализует вышеуказанные операции с односвязными списками.

# -*- coding: utf-8 -*-
# @Time      : 2019-10-30 15:50
# @Author    : yuzhou_1su
# @ContactMe : https://blog.csdn.net/yuzhou_1shu
# @File      : singly_linked_list.py
# @Software  : PyCharm


class Node(object):
    """声明节点"""

    def __init__(self, element):
        self.element = element  # 给定一个元素
        self.next = None  # 初始设置下一节点为空


class Singly_linked_list:
    """Python实现单链表"""

    def __init__(self):
        self.__head = None  # head设置为私有属性，禁止外部访问

    def is_empty(self):
        """判断链表是否为空"""
        return self.__head is None

    def length(self):
        """返回链表长度"""
        cur = self.__head  # cur游标，用来移动遍历节点
        count = 0  # count记录节点数量
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    def travel_list(self):
        """遍历整个链表，打印每个节点的数据"""
        cur = self.__head
        while cur is not None:
            print(cur.element, end=" ")
            cur = cur.next
        print("\n")

    def insert_head(self, element):
        """头插法：在单链表头部插入一个节点"""
        newest = Node(element)  # 创建一个新节点
        if self.__head is not None:  # 如果初始不为空，就将新节点的"next"指针指向head
            newest.next = self.__head
        self.__head = newest  # 把新节点设置为head

    def insert_tail(self, element):
        """尾插法：在单链表尾部增加一个节点"""
        if self.__head is None:
            self.insert_head(element)  # 如果这是第一个节点，调用insert_head函数
        else:
            cur = self.__head
            while cur.next is not None:  # 遍历到最后一个节点
                cur = cur.next
            cur.next = Node(element)  # 创建新节点并连接到最后

    def insert(self, pos, element):
        """指定位置插入元素"""

        # 如果位置在0或者之前，调用头插法
        if pos < 0:
            self.insert_head(element)
        # 如果位置在原链表长度之后，调用尾插法
        elif pos > self.length() - 1:
            self.insert_tail(element)
        else:
            cur = self.__head
            count = 0
            while count < pos - 1:
                count += 1
                cur = cur.next
            newest = Node(element)
            newest.next = cur.next
            cur.next = newest

    def delete_head(self):
        """删除头结点"""
        cur = self.__head
        if self.__head is not None:
            self.__head = self.__head.next
            cur.next = None
        return cur

    def delete_tail(self):
        """删除尾节点"""
        cur = self.__head
        if self.__head is not None:
            if self.__head.next is None:  # 如果头结点是唯一的节点
                self.__head = None
            else:
                while cur.next.next is not None:
                    cur = cur.next
                cur.next, cur = (None, cur.next)
        return cur

    def remove(self, element):
        """删除指定元素"""
        cur, prev = self.__head, None
        while cur is not None:
            if cur.element == element:
                if cur == self.__head:  # 如果该节点是头结点
                    self.__head = cur.next
                else:
                    prev.next = cur.next
                break
            else:
                prev, cur = cur, cur.next
        return cur.element

    def modify(self, pos, element):
        """修改指定位置的元素"""
        cur = self.__head
        if pos < 0 or pos > self.length():
            return False
        for i in range(pos - 1):
            cur = cur.next
        cur.element = element
        return cur

    def search(self, element):
        """查找节点是否存在"""
        cur = self.__head
        while cur:
            if cur.element == element:
                return True
            else:
                cur = cur.next
        return False

    def reverse_list(self):
        """反转整个链表"""
        cur, prev = self.__head, None
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        self.__head = prev


def main():
    List1 = Singly_linked_list()
    print("链表是否为空", List1.is_empty())

    List1.insert_head(1)
    List1.insert_head(2)
    List1.insert_tail(3)
    List1.insert_tail(4)
    List1.insert_tail(5)

    length_of_list1 = List1.length()
    print("插入节点后，List1 的长度为：", length_of_list1)

    print("遍历并打印整个链表: ")
    List1.travel_list()

    print("反转整个链表: ")
    List1.reverse_list()
    List1.travel_list()

    print("删除头节点: ")
    List1.delete_head()
    List1.travel_list()

    print("删除尾节点: ")
    List1.delete_tail()
    List1.travel_list()

    print("在第二个位置插入5: ")
    List1.insert(1, 5)
    List1.travel_list()

    print("在第-1个位置插入100：")
    List1.insert(-1, 100)
    List1.travel_list()

    print("在第100个位置插入2：")
    List1.insert(100, 2)
    List1.travel_list()

    print("删除元素5：")
    print(List1.remove(5))
    List1.travel_list()

    print("修改第5个位置的元素为7: ")
    List1.modify(5, 7)
    List1.travel_list()

    print("查找元素1:")
    print(List1.search(1))


if __name__ == "__main__":
    main()

вывод результатов теста

链表是否为空 True
插入节点后，List1 的长度为： 5
遍历并打印整个链表: 
2 1 3 4 5 

反转整个链表: 
5 4 3 1 2 

删除头节点: 
4 3 1 2 

删除尾节点: 
4 3 1 

在第二个位置插入5: 
4 5 3 1 

在第-1个位置插入100：
100 4 5 3 1 

在第100个位置插入2：
100 4 5 3 1 2 

删除元素5：
5
100 4 3 1 2 

修改第5个位置的元素为7: 
100 4 3 1 7 

查找元素1:
True

Суммировать

После того, как мы освоим эти основные операции, я рекомендую метод обучения, заключающийся в выполнении упражнений, связанных с односвязными списками в Интернете (таких как LeetCode). Какие есть хорошие упражнения? Позже я напишу в блоге, чтобы найти несколько классических вопросов и записать идеи. Если вы найдете хороший вопрос, поделитесь им со мной, изучите и обсудите вместе.