数据结构之链表

1. 链表是以节点的形式来存储，是链式存储
2. 每个节点蕴含 data 域，next 域：指向下一个节点
3. 链表的各个节点不肯定是间断存储
4. 链表分带头节点的链表和没有头节点的链表，依据理论的需要来确定

单链表

a. 减少节点思路剖析
借助辅助节点，找到最初一个节点的 next 指向新节点
b. 删除节点思路剖析
借助辅助节点，找到删除节点的前一个节点 temp
temp.next = temp.next.next
c. 批改节点思路剖析
借助辅助节点，遍历找到该节点而后批改
d. 遍历链表思路剖析
借助辅助节点，遍历
e. 获取到单链表的节点的个数
遍历，累加
f. 查找单链表中的倒数第 k 个节点
遍历至总长度 - k 的节点即为倒数第 k 个节点
g. 单链表的反转
新建反转头节点 reverseHead，遍历原链表，将节点一个个插入反转俩表的第一个节点，最初再把 head.next = reverseHead.next
h. 从头到尾打印单链表
用栈先进后出个性

import java.util.Stack;

public class SingleLinkedListDemo {public static void main(String[] args) {SingleLinkedList singleLinkedList = new SingleLinkedList();
        Node node1 = new Node(1,"1");
        Node node2 = new Node(2,"2");
        Node node3 = new Node(3,"3");
        Node node4 = new Node(4,"4");
        singleLinkedList.add(node1);
        singleLinkedList.add(node2);
        singleLinkedList.add(node3);
        singleLinkedList.add(node4);
        singleLinkedList.list();

//        singleLinkedList.del("3");
//        singleLinkedList.list();

//        singleLinkedList.update(new Node(2,"10"));
//        singleLinkedList.list();

//        singleLinkedList.reversetList();
//        singleLinkedList.list();

        singleLinkedList.reversePrint();}
}

class SingleLinkedList {
    // 先初始化一个头节点, 头节点不要动
    private Node head = new Node(0,"");

    // 增加节点到单向链表
    //1. 找到以后链表的最初节点
    //2. 将最初这个节点的 next 指向新的节点
    public void add(Node Node) {

        // 因为 head 节点不能动，因而咱们须要一个辅助遍历 temp
        Node temp = head;
        // 遍历链表，找到最初
        while (temp.next != null) {temp = temp.next;}
        // 当退出 while 循环时，temp 就指向了链表的最初
        // 将最初这个节点的 next 指向新的节点
        temp.next = Node;
    }

    // 批改节点的信息, 依据 no 编号来批改
    public void update(Node newNode) {
        // 找到须要批改的节点, 依据 no 编号
        // 定义一个辅助变量
        Node temp = head.next;
        while(temp != null) {if(temp.index == newNode.index) {
                temp.data = newNode.data;
                break;
            }
            temp = temp.next;
        }
    }

    // 删除节点
    // 咱们在比拟时，是 temp.next.data 和须要删除的节点的 data 比拟
    public void del(String data) {
        Node temp = head;
        while (temp.next != null) {if (temp.next.data.equals(data)) {
                temp.next = temp.next.next;
                break;
            }
            temp = temp.next; //temp 后移，遍历
        }
    }

    // 显示链表[遍历]
    public void list() {
        Node temp = head.next;
        while (temp != null) {System.out.println(temp.data);
            // 将 temp 后移
            temp = temp.next;
        }
    }

    // 获取到单链表的节点的个数, 不统计头节点
    public int getLength() {
        int length = 0;
        Node temp = head.next;
        while (temp != null) {
            length ++;
            // 将 temp 后移
            temp = temp.next;
        }
        return length;
    }

    // 查找单链表中的倒数第 k 个结点
    //1. 编写一个办法，一个 k
    //2. k 示意是倒数第 k 个节点
    //3. 先把链表从头到尾遍历，失去链表的总的长度 getLength
    //4. 失去 size 后，咱们从链表的第一个开始遍历 (size-k)个，就能够失去
    //5. 如果找到了，则返回该节点，否则返回 null
    public Node findLastKNode(int k) {
        // 判断如果链表为空，返回 null
        if(head.next == null) {return null;// 没有找到}
        // 第一个遍历失去链表的长度(节点个数)
        int size = getLength();
        // 第二次遍历  size-k 地位，就是咱们倒数的第 K 个节点
        // 先做一个 k 的校验
        if(k <=0 || k > size) {return null;}
        // 定义给辅助变量，for 循环定位到倒数的 index
        Node temp = head.next; //3 // 3 - 1 = 2
        for(int i =0; i< size-k; i++) {temp = temp.next;}
        return temp;
    }

    // 将单链表反转
    public void reversetList() {
        // 如果以后链表为空，或者只有一个节点，无需反转，间接返回
        if(head.next == null || head.next.next == null) {return;}

        // 定义一个辅助的指针(变量)，帮忙咱们遍历原来的链表
        Node cur = head.next;
        Node next = null;// 指向以后节点 cur 的下一个节点
        Node reverseHead = new Node(0, "");
        // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端
        while(cur != null) {
            next = cur.next;// 先临时保留以后节点的下一个节点，因为前面须要应用
            cur.next = reverseHead.next;// 将 cur 的下一个节点指向新的链表的第一个节点
            reverseHead.next = cur; // 将 cur 连贯到新的链表上
            cur = next;// 让 cur 后移
        }
        // 将 head.next 指向 reverseHead.next , 实现单链表的反转
        head.next = reverseHead.next;
    }

    // 能够利用栈这个数据结构，将各个节点压入到栈中，而后利用栈的先进后出的特点，就实现了逆序打印的成果
    public void reversePrint() {if(head.next == null) {return;// 空链表，不能打印}
        // 创立要给一个栈，将各个节点压入栈
        Stack<Node> stack = new Stack<Node>();
        Node cur = head.next;
        // 将链表的所有节点压入栈
        while(cur != null) {stack.push(cur);
            cur = cur.next; //cur 后移，这样就能够压入下一个节点
        }
        // 将栈中的节点进行打印,pop 出栈
        while (stack.size() > 0) {System.out.println(stack.pop().data); //stack 的特点是先进后出
        }
    }
}

// 定义 Node
class Node {
    public int index;// 序号
    public String data;// 数据
    public Node next; // 指向下一个节点

    public Node(int index,String data) {
        this.index = index;
        this.data = data;
    }
}

双向链表

双向链表的节点比单链表多一个 pre 节点
a. 减少节点思路剖析
与单链表一样，借助辅助节点，找到最初一个节点的 next 指向新节点，但双向链表的新节点还需指向最初一个节点

temp.next = newNode;
newNode.pre = temp;

b. 删除节点思路剖析
与单链表不同，能够实现节点的自我删除，找到这个节点 temp

temp.pre.next = temp.next;
if(temp.next != null){
// 若最初一个节点执行上面代码则会报空指针异样，temp.next = null
temp.next.pre = tem.prel; 
}

c. 批改节点思路剖析
与单链表一样，借助辅助节点，遍历找到该节点而后批改
d. 遍历链表思路剖析
与单链表一样，借助辅助节点，向后遍历

环形链表和约瑟夫问题

//TODO