Skip to content

Latest commit

 

History

History
33 lines (28 loc) · 1.93 KB

File metadata and controls

33 lines (28 loc) · 1.93 KB

LeetCode链表

1.定义

链表是一种物理存储单元上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现。

链表中每个元素称为节点,节点包括两部分,一是存储数据元素的数据域,一是存储下一个节点地址的指针域。

由于不必按照顺序存储,链表插入和删除元素的时间复杂度O(1),查找元素的时间复杂度O(n)

2.数组与链表比较、

  • 从逻辑结构方面,两者都属于线性表,数组是顺序存储结构的线性表,链表是链式存储结构的线性表。
  • 从物理内存方面,数组占用的是一段连续的内存区,链表在内存中是非连续的,分散的,是通过指针实现逻辑上的线性表。
  • 对于访问,由于数组在内存上是连续的,所以支持“随机访问”,时间复杂度O(1),而链表是非连续的内存空间,只能通过“顺序访问”,时间复杂度O(n)
  • 对于插入/删除元素,数组的时间复杂度O(n),链表的时间复杂度O(1)

3.题目