单向链表

[Zakariyya]

• 有序列表，各节点不一定是连续存储
• data域（数据元素）
• next域（指向下一个节点）
• 链表分 带头的链表 和 没有头节点的链表 ，根据实际的需求来确定

创建

思路

1. 创建一个head头节点，作用是表示单链表的头部，data=null,next指向下一个节点
2. 后面我们每添加一个节点，就直接加入到 链表的最后（链表的结尾用next=null来判断）

添加

思路，当不考虑编号排序时

1. 遍历链表
2. 找到当前链表的最后一个节点
3. 将最后这个节点的next 指向新的节点

   
   private Node head = new Node(0,'','');

public void add(Node node){

//因为head节点不能动，因此需要一个辅助变量temp
Node temp = head;

//遍历链表，找到最后
while(true){
    if(temp.next==nulll){
        break;
    }
    temp = temp.next;
}
//当退出while循环时，temp就指向了链表的最后
// 将最后这个节点的next，指向新的节点
temp.next = node;

}

## 显示链表 【遍历啊~ 】
```java
public void list(){

    //判断链表是否为空
    if(head.next == null)
        return ;

    Node temp = head;
    while(true){
        //判断是否在链表最后
        if(temp.next == null)
            break;

        //输出信息
        sout(temp);
        //然后把temp后移，一定要
        temp = temp.next;
    }

}

中间插入

思路

1. A、B、D，在B、D 中间插入C
2. 遍历链表，找到B，然后找到D
3. 将C的 next 指向D
4. B的 next 指向C

删除节点

思路

1. A、B、C、D，在B、D 中间删除C
2. 需要找到 待删除节点 的前一个节点：B
3. 遍历链表，找到B，然后找到D
4. 将B的 next 指向D
5. 没被引用对象就会被GC回收掉

小题

查找单链表中倒数的第K个节点

思路

1. index 接收，表示是倒数第index个节点
2. 遍历链表，得到链表总长度 size
3. 得到size，再从头遍历，第（size-index）个，就可以得到
4. 如果找得到，就返回该节点，否则返回null

单链表的反转

遍历A链表，将每次遍历到的元素，都加到链表的头部中

单链表的逆向打印

思路

1. 方式1：先将单链表进行反转操作，然后再遍历即可，这样的问题会破坏原来单链表的结构，不建议
2. 方式2：可以利用 栈（Stack） 这个结构，将各个节点压入栈中，利用栈的结构实现逆序打印的效果。

   Stack 的使用