链表是什么

链表了解吗

• Linked list is a sequence of links which contains items

• Link - Each link of a linked list can store a data called an element

• Next - Each link of a linked list contains a link to the next link called Next

• LinkedList - A Linked List contains the connection link to the first link called First

• Linked list can be visualized as a chain of nodes,where every node points to hte next node

  ![image](

  • Simple linked list -item navigation is forward only
  • doubly linked list - items can be navigated forward and backward
  • circular linked list - last item contains link of the first element as next and the first element has a link to the last element as previous.

双向链表是什么

同上，节点有前后指针

跟数组的区别

• 数组在编译时已经分配好连续内存
• 链表在运行时添加数据时分配内存
• 数组在栈，链表在堆

数组为什么快

• 数组查找快，因为可以根据索引直接获得，复杂度O(1),链表复杂度O(N)
• 数组插入和删除慢，因为空间连续，插入删除后需要整理内存大小，链表插入删除快，只要改变指针指向即可

参考：1. https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm

2.https://www.studytonight.com/data-structures/linked-list-vs-array