2-链表.md

链表&栈&队列

1. 链表

单向链表和双向链表的优缺点及使用场景

单向链表：只有一个指向下一个节点的指针。

• 优点：单向链表增加删除节点简单。遍历时候不会死循环；

• 缺点：只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。

  适用于节点的增加删除。

双向链表：有两个指针，一个指向前一个节点，一个后一个节点。

• 优点：可以找到前驱和后继，可进可退；

• 缺点：增加删除节点复杂，需要多分配一个指针存储空间。

适用于需要双向查找节点值的情况。

1.1 单向链表

1.2 双向链表

1.2.1 clear细节

public void clear() {
    size=0;
    first=null;
    last=null;
}

当first结点和last都不指向链表时，链表将会被jvm回收

原因，只有被gc root指向的对象才不会被回收

常见的gc root有：

• 被栈指针指向的对象（即被局部变量所指向的对象）

2. 练习题

约瑟夫问题

n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

解决方案：使用双向循环链表

2. 栈

接口设计