备战蓝桥杯Day17 - 链表

链表

基本概念

��表是由一系列节点组成的元素集合。

每个节点包含两部分：数据域 item 、指向下一个节点的指针 next

通过节点之间的相互链接，形成一个链表

1. 链表的初始化

# 手动建立链表# 链表的初始化class Node(object):    def __init__(self, item):        self.item = item        self.next = next# 手动添加链表中的数据a = Node(1)b = Node(2)c = Node(3)d = Node(4)# 将节点之间链接起来a.next = bb.next = cc.next = d# 可通过指针输出想要的数据print(a)  # 1print(a.next)  # 2print(a.next.next)  # 3print(a.next.next.next)  # 4 

手动添加数据的方式我们不怎么用，有专门的创建链表的方法 ，手动创建我们只需知道了解即可。

2.创建链表

(1).头插法

先把新的节点连到头节点（head）前面

 再把头节点head挪到这个新的元素上

代码实现

def creat_linklist_head(li):    head = Node(li[0])   # 将列表中的第一个元素设为头节点    for element in li[1:]:   # 循环遍历链表        node = Node(element)  # 将链表中的元素设置为一个节点        node.next = head   # 将元素直接插到头节点的前面        head = node   # 再将头节点直接挪到前面    return head   # 返回头节点

(2).尾插法 

 将尾指针指向下一个元素。

 再把尾指针先后挪。

代码实现

def creat_linklist_tail(li):    head = Node(li[0])  # 将列表中的第一个元素设为头节点    tail = head  # 当一开始只有一个节点的时候，头节点和尾节点是同一个    for element in li[1:]:  # 循环遍历列表读取数据        node = Node(element)   # 将列表中的元素设置为一个节点        tail.next = node  # 将尾指针指向新添加的元素        tail = node  # 尾指针向后移，移到最后一个元素上    return head  # 返回头节点

3.遍历链表

当链表不为空时，直接循环打印当前元素，并不断指向下一个。

def print_linklist(lk):    while lk:        print(lk.item, end=" ")        lk = lk.next# 集合尾插法进行测试lk = creat_linklist_tail([1,2,3,4])print_linklist(lk)

运行后可以正常给出遍历结果，但是我不理解他为什么会报错，我跟着视频中教程敲得代码，人家没报错为什么我的报错。等我研究研究。

 4.在指定位置插入元素

实现在3和5之间插入数字4.

 为了防止数据丢失，首先把节点4连到节点5上，将p.next -> curNode.next

 再将curNode的指针指向p，实现链接。curNode.next -> p

 代码实现

class LinkedList:      def __init__(self):          self.head = None        def insert(self, data, position=0):          new_node = Node(data)            if self.head is None:              self.head = new_node              return            if position == 0:              new_node.next = self.head              self.head = new_node              return            current = self.head          index = 0            while current is not None and index