算法与Python

算法与Python 知识量:10 - 40 - 100

2.3 链表><

什么是单链表- 2.3.1 -

单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成包括两个部分:一个是存储数据的数据域,另一个是指向下一个结点的指针域。单链表又分为无头节点的单链表和带头节点的单链表。在单链表中,每个结点只有一个链域,因此每个结点只有一个直接后继。此外,链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起。

需要注意的是,在对单链表进行插入、删除、查找等操作时,需要时刻注意指针是否非法操作,以避免程序崩溃等问题。此外,链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。

建立单链表- 2.3.2 -

在Python中,可以使用类来创建单链表。以下是一个简单的示例:

class Node:  
    def __init__(self, data=None):  
        self.data = data  
        self.next = None  
  
class LinkedList:  
    def __init__(self):  
        self.head = None  
  
    def insert(self, data):  
        if not self.head:  
            self.head = Node(data)  
        else:  
            current = self.head  
            while current.next:  
                current = current.next  
            current.next = Node(data)  
  
    def print_list(self):  
        current = self.head  
        while current:  
            print(current.data)  
            current = current.next

在这个示例中,定义了两个类:Node和LinkedList。Node类代表链表中的一个节点,包含数据和指向下一个节点的指针。LinkedList类代表整个链表,包含一个指向链表头部的指针。LinkedList类有两个方法:insert用于在链表的末尾插入新的节点,print_list用于打印链表中的所有节点。

建立双链表- 2.3.3 -

双链表是一种链表,其中每个节点都有两个链接,一个指向前一个节点,另一个指向下一个节点。在Python中,可以使用类来创建双链表。以下是一个简单的示例:

class Node:  
    def __init__(self, data=None):  
        self.data = data  
        self.next = None  
        self.prev = None  
  
class DoublyLinkedList:  
    def __init__(self):  
        self.head = None  
  
    def insert_at_beginning(self, data):  
        if not self.head:  
            new_node = Node(data)  
            new_node.next = self.head  
            self.head = new_node  
        else:  
            new_node = Node(data)  
            new_node.next = self.head  
            new_node.prev = self.head.prev  
            self.head.prev.next = new_node  
            self.head = new_node  
  
    def print_list(self):  
        current = self.head  
        while current:  
            print(current.data)  
            current = current.next

在这个示例中,定义了两个类:Node和DoublyLinkedList。Node类代表双链表中的一个节点,包含数据和两个链接,一个指向前一个节点,另一个指向下一个节点。DoublyLinkedList类代表整个双链表,包含一个指向链表头部的指针。DoublyLinkedList类有一个方法:insert_at_beginning用于在链表的开头插入新的节点,print_list用于打印链表中的所有节点。

向单链表中添加元素- 2.3.4 -

如果有一个单链表的节点类(Node)和一个单链表类(LinkedList),可以使用以下方法向单链表中添加元素:

class Node:  
    def __init__(self, data=None):  
        self.data = data  
        self.next = None  
  
class LinkedList:  
    def __init__(self):  
        self.head = None  
  
    def append(self, data):  
        if not self.head:  
            self.head = Node(data)  
        else:  
            current = self.head  
            while current.next:  
                current = current.next  
            current.next = Node(data)

在这个示例中,定义了两个类:Node和LinkedList。Node类代表单链表中的一个节点,包含数据和指向下一个节点的指针。LinkedList类代表整个单链表,包含一个指向链表头部的指针。LinkedList类有一个方法:append用于在链表的末尾添加新的节点。

向双链表中添加元素- 2.3.5 -

如果有一个双链表的节点类(Node)和一个双链表类(DoublyLinkedList),可以使用以下方法向双链表中添加元素:

class Node:  
    def __init__(self, data=None):  
        self.data = data  
        self.next = None  
        self.prev = None  
  
class DoublyLinkedList:  
    def __init__(self):  
        self.head = None  
  
    def append(self, data):  
        if not self.head:  
            new_node = Node(data)  
            new_node.next = self.head  
            self.head = new_node  
        else:  
            new_node = Node(data)  
            new_node.next = None  
            new_node.prev = self.head.prev  
            self.head.prev.next = new_node  
            self.head = new_node

在这个示例中,定义了两个类:Node和DoublyLinkedList。Node类代表双链表中的一个节点,包含数据和两个链接,一个指向前一个节点,另一个指向下一个节点。DoublyLinkedList类代表整个双链表,包含一个指向链表头部的指针。DoublyLinkedList类有一个方法:append用于在链表的末尾添加新的节点。

删除列表中的元素- 2.3.6 -

在Python中,可以使用几种不同的方法从列表中删除元素。以下是其中的一些:

1. 使用remove()方法:这个方法会删除列表中第一个匹配的元素。

list1 = [1, 2, 3, 2, 4, 2]    
list1.remove(2)    
print(list1)  # 输出: [1, 3, 4, 2]

注意,如果要删除的元素不存在于列表中,remove()方法会引发一个ValueError。

2. 使用pop()方法:这个方法会删除并返回指定索引的元素。如果不提供索引,它会删除并返回列表的最后一个元素。

list1 = [1, 2, 3, 4, 5]    
removed_element = list1.pop(2)    
print(removed_element)  # 输出: 3      
print(list1)  # 输出: [1, 2, 4, 5]

3. 使用del语句:这个语句可以用来删除整个列表,或者列表中的特定元素。

list1 = [1, 2, 3, 4, 5]    
del list1[2]    
print(list1)  # 输出: [1, 2, 4, 5]

4. 使用列表推导式:这个方法可以用来删除满足特定条件的元素。

list1 = [1, 2, 3, 4, 5]    
list1 = [x for x in list1 if x != 3]    
print(list1)  # 输出: [1, 2, 4, 5]

在上述例子中,列表推导式创建了一个新的列表,只包含那些不等于3的元素。原列表list1被这个新列表替代,因此原来的元素3被删除。