java复习篇 数据结构：链表第一节

目录

单向链表

初始

头插

思路

情况一

情况二

代码

尾插

思路

遍历

优化遍历

遍历验证头插

尾插代码

优化

尾插测试

get

思路

代码

测试

insert

思路

代码

优化

测试

remove

移除头结点

提问

移除指定位置

测试

---

单向链表

每个元素只知道自己的下一个元素是谁，最后一个元素的下一个元素为null

初始

public class SingleLinkedList {
    
    // 头指针
    private Node head;

    // 节点类      private对外隐藏细节
    @Data
    @AllArgsConstructor
    private static class Node {
        private int value;
        private Node next;
    }

}

将内部类定义为静态主要有两个原因：

1. 实例化方式：静态内部类的实例化不需要依赖于外部类。而普通的内部类在实例化时会隐含地包含一个对外部类的引用，因此，普通的非静态内部类不能脱离外部类实例而单独存在。
2. 访问方式：静态内部类可以使用静态方法直接通过类名来访问外部类的静态成员，而不需要创建外部类的实例。而普通的内部类需要先创建外部类的实例，然后通过该实例来访问外部类的静态成员。

头插

思路

对于使用者来说，我给你一个value值，你要将我的这个value值放入到链表头结点处

情况一

一开始，无节点，现在新增一个新节点

head = new Node(value, null);

情况二

一开始，有节点，现在新增一个新节点

head = new Node(value, head);

新节点的next指针指向原来节点，原来节点地址为头指针指向的地址

代码

    public void addFirst(int value) {
        head = new Node(value, head);
    }

为什么没有情况一？

开始时，head为null，情况二包含情况一

尾插

思路

对于使用者来说，我给你一个value值，你要将我的这个value值放入到链表最后面

那我怎么知道你链表什么时候是最后面？

遍历

遍历到最后一个节点，此时它的next指针指向null

注意：头指针是为了记录第一个节点地址，不能动，所以我定义一个可以移动的指针开始指向第一个节点

    public void foreach() {
        Node p = head;
        while (p != null) {
            System.out.println(p.value);
            p = p.next;
        }
    }

优化遍历

实际开发中，你可能不是要打印，而是对加进来的值有其他操作，此时，换成函数式编程

    public void foreach(Consumer<Integer> consumer) {
        Node p = head;
        while (p != null) {
            consumer.accept(p.value);
            p = p.next;
        }
    }

遍历验证头插

public class Test {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addFirst(8);
        singleLinkedList.addFirst(7);
        singleLinkedList.addFirst(6);
        singleLinkedList.addFirst(5);
        singleLinkedList.foreach(System.out::println);
    }
}

为什么是倒序？

头插，先插的会随着后续插入一次次向后挪动

尾插代码

通过遍历，可以知道指针指向过最后一个节点后，然后指向了null

那让指针一直指，最后一次的下一个节点不为null时，为我们所需要的节点

    public void addLast(int value) {
        Node p = head;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new Node(value, null);
    }

存在问题：如果我链表啥也没有，那么p.next直接空指针

优化

链表什么也没有，此时添加元素不就是头插嘛

    public void addLast(int value) {
        if (head == null) {
            addFirst(value);
            // 不要忘记return，否则会有相同值
            return;
        }
        Node p = head;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new Node(value, null);
    }

尾插测试

public class Test {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(8);
        singleLinkedList.addLast(7);
        singleLinkedList.addLast(6);
        singleLinkedList.addLast(5);
        singleLinkedList.foreach(System.out::println);
    }
}

get

思路

list(index)? 是通过给一个索引，然后得到该索引对应位置的值。

对于链表，给一个索引，返回该节点的值。

代码

    public int get(int index) {
        int i = 0;
        Node p = head;
        while (p != null) {
            if (i == index) {
                return p.value;
            } else {
                p = p.next;
                i++;
            }
        }
        throw  new IllegalArgumentException("索引越界异常");
    }

也可以用for循环写

public Node findNode(int index) {
    int i = 0;
    for (Node p = head; p != null; p = p.next, i++) {
        if (i == index) {
            return p;
        }
    }
    return null;
}

public int get(int index) {
    Node node = findNode(index);
    if (node == null) {
        throw new IllegalArgumentException(StringUtils.format("索引: {} 不合法", index));
    }
    return node.value;
}

测试

public class Test {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(8);
        singleLinkedList.addLast(7);
        singleLinkedList.addLast(6);
        singleLinkedList.addLast(5);
        singleLinkedList.foreach(System.out::println);
        System.out.println("====");
        System.out.println(singleLinkedList.get(0));
    }
}

insert

思路

我要向某个位置插入某个值，那么我需要知道这个位置的前面一个节点(其next 指向当前位置)

代码

    public void insert(int index, int value) {
        Node 前节点 = findNode(index - 1);
        if (前节点 == null) throw new IllegalArgumentException("索引越界异常");
        前节点.next = new Node(value, 前节点.next);
    }

    private Node findNode(int index) {
        int i = 0;
        Node p = head;
        while (p != null) {
            if (i == index) {
                return p;
            } else {
                p = p.next;
                i++;
            }
        }
        return null;
    }

index = 0时，此时返回null，抛出异常，显然不对

优化

index=0时插入，即头插

    public void insert(int index, int value) {
        if (index == 0) {
            addFirst(value);
            return;
        }
        Node 前节点 = findNode(index - 1);
        if (前节点 == null) throw new IllegalArgumentException("索引越界异常");
        前节点.next = new Node(value, 前节点.next);
    }

测试

public class Test {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(8);
        singleLinkedList.addLast(7);
        singleLinkedList.addLast(6);
        singleLinkedList.addLast(5);
        singleLinkedList.foreach(System.out::println);
        System.out.println("====");
        singleLinkedList.insert(2, 100);
        singleLinkedList.foreach(System.out::println);
    }
}

remove

移除头结点

    public void removeFirst() {
        if (head == null) {
            return;
        }
        head = head.next;
    }

提问

1这个节点还存在，有没有因此而造成内存泄露？

不会，1节点无引用指向他，JVM垃圾回收会处理

移除指定位置

    public void remove(int index) {
        if (index == 0) {
            removeFirst();
            return;
        }
        Node 前节点 = findNode(index - 1);
        if (前节点 == null) throw new IllegalArgumentException("索引越界异常");
        前节点.next = 前节点.next.next;
    }

测试

public class Test {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(8);
        singleLinkedList.addLast(7);
        singleLinkedList.addLast(6);
        singleLinkedList.addLast(5);
        singleLinkedList.foreach(System.out::println);
        System.out.println("====");
        singleLinkedList.insert(2, 100);
        singleLinkedList.foreach(System.out::println);
        System.out.println("====");
        singleLinkedList.remove(4);
        singleLinkedList.foreach(System.out::println);
    }
}