链表

链表

链表

数组和链表的对比：

特点：

​ 真正的动态；头插方便

在链表中插入元素：

顺序很重要

Node node = new Node(e)
node.next = prev.next;
prev.next = node;

在链表中删除某个节点：

Node node = new Node(e)
Node delNode = prev.next;
prev.next=delNode.next;
delNode.next = null;
size --;

链表的时间复杂度：

1. 添加、删除操作

   • addLast(e) ——-O(n)
   • addFirst(e)——–O(1)
   • add(index,e)——-O(n/2)=O(n)

2. 查找操作O(n)

链表的应用

• 用链表实现栈
• 用链表实现队列

删除元素递归的微观机制解读：

递归调用的代价：函数调用+系统栈空间