Day3-渐渐明白[链表]的边界

代码随想录算法训练营Day3

链表理论基础

链表是通过指针串联在一起的数据结构.链表的入口处被称为head.

单链表:每个节点由两部分组成,一个是数据域,一个是指针域,(存放指向下一个节点的指针),最后一个节点的指针域指向null.(单链表中的指针域只指向节点的下一个节点.)

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点.(双链表 既可以向前查询也可以向后查询.)

循环链表: 单链表的最后一个节点指针指向head.

数组是在内存中是连续分布的，但是链表在内存中不是连续分布的。链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

leetcode把链表默认定义好了,**面试时,注意如何定义链表.**删除节点在C++中,要手动释放节点.

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
1
2
3
4

链表的增添和删除都是O(1)操作,也不会影响到其他节点.

注意: 链表中删除头节点: head = head.next;链表中删除中间节点: node3.next = node5(node4被删除).

增加虚拟头结点 dummyHead可以把两种删除方法统一处理.

性能分析