数据结构学习笔记——单链表

链表介绍 链表(linked list)是一种在物理上非连续,非顺序的数据结构,由若干节点(node)组成 单链表每一个节点又包含两部分,1是存放数据的变量data,2是存放指向下一个结点的指针next 双向链表每一个节点包含三部分,在单链表的基础上多了一个指向前置节点的prev指针 链表的第一个节点被称为头节点,最后一个节点被称为尾节点,尾结点的next指针指向null 链表在内存中的存储方式为随机存储 时间复杂度 不考虑插入,删除操作之前的查找元素的过程,只考虑插入和删除,时间复杂度为O(1) 链表的查找从头结点开始,链表的长度越大,查找的时间越长,时间复杂度为O(n) 对比数组和链表 数