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