链表

顺序表性质

• 链表不同于顺序表，顺序表底层采用数组作为存储容器，需要分配一块连续且完整的内存空间进行使用，而链表则不需要，它通过一个指针来连接各个分散的结点，形成了一个链状的结构，每个结点存放一个元素，以及一个指向下一个结点的指针，通过这样一个一个相连，最后形成了链表。

• 链表不需要申请连续的空间，只需要按照顺序连接即可，虽然物理上可能不相邻，但是在逻辑上依然是每个元素相邻存放的，这样的结构叫做链表（单链表）。

• 链表分为带头结点的链表和不带头结点的链表，戴头结点的链表就是会有一个头结点指向后续的整个链表，但是头结点不存放数据：

• 而不带头结点的链表就像上面那样，第一个节点就是存放数据的结点，一般设计链表都会采用带头结点的结构，因为操作更加方便。

链表的基本属性

public class LinkListt<E> 泛型E，因为表中要存的具体数据类型待定

• 以下节点代码可以理解为就是上述图中的一个小圈/一个节点

private static class Node<E> {  //结点类，仅供内部使用
    E element;   //每个结点都存放元素
    Node<E> next;   //指向下一个结点的引用
    //因为链表一个节点需要存储值和指向下个节点(可理解就是指向另一个节点)

    public Node(E element) {//通过构造函数赋值
        this.element = element;
    }
}

private final Node<E> head = new Node<>(null);链表的头结点，用于连接之后的所有结点

链表的插入和删除

插入思路

删除思路

链表插入代码

• if (index < 0 || index > size)判断插入的合法性
• Node<E> prev = head;先找到对应位置的前驱结点(头节点)
• for (int i = 0; i < index; i++)寻找到需要插入的索引号的前一位
• Node<E> node = new Node<>(element);创建新的结点,并将需要插入的值用构造方法存储
• node.next = prev.next;

public void add(E element, int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("插入位置非法，合法的插入位置为：0 ~ " + size);
    Node<E> prev = head;   //先找到对应位置的前驱结点
    for (int i = 0; i < index; i++)
        prev = prev.next;
    Node<E> node = new Node<>(element);//创建新的结点,并将需要插入的值用构造方法存储
    node.next = prev.next;   //先让新的节点指向原本在这个位置上的结点
    prev.next = node;   //然后让前驱结点指向当前结点
    size++;   //完事之后一样的，更新size
}

链表删除代码

• for (int i = 0; i < index; i++)寻找到需要插入的索引号的前一位
• prev.next = prev.next.next; 直接将删除节点的下一位赋值会前一位的next(此时还未真的删除,因此可以使用prev.next.next)

public E remove(int index) {
    if (index < 0 || index > size - 1)   //同样的，先判断位置是否合法
        throw new IndexOutOfBoundsException("删除位置非法，合法的删除位置为：0 ~ " + (size - 1));
    Node<E> prev = head;
    for (int i = 0; i < index; i++)   //同样需要先找到前驱结点
        prev = prev.next;
    E e = prev.next.element;   //先把待删除结点存放的元素取出来
    prev.next = prev.next.next;  //可以删了
    size--;   //记得size--
    return e;
}

链表更新代码

public void setElement(int index, E e) {
    if (index < 0 || index > size - 1)
        throw new IndexOutOfBoundsException("更新位置非法，合法的删除位置为：0 ~ " + (size - 1));
    //获取指定位置的原节点
    Node<E> node = head;
    //同样需要先找到前驱结点
    for (int i = 0; i < index; i++) node = node.next;//需要到达更新节点的前一节点
    node.next.element = e;
}

链表查询代码

• while (index-- >= 0)while循环搭配node = node.nextindex值依次递减,而节点也会依次指向下一个节点

public E getElement(int index) {
    if (index < 0 || index > size - 1)
        throw new IndexOutOfBoundsException("非法的位置，合法的位置为：0 ~ " + (size - 1));
    Node<E> node = head;
    while (index-- >= 0)   //这里直接让index减到-1为止
        node = node.next;
    return node.element;
}

链表toString

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("链表长度: ").append(getSize()).append(" ");

        Node<E> node = head.next;   //从第一个结点开始，一个一个遍历，遍历一个就拼接到字符串上去
        builder.append("链表元素: ").append(" ");
        while (node != null) {
            builder.append(node.element).append(" ");
            node = node.next;
        }
        return builder.toString();
    }
}

总代码

• Main代码

import ClassStudy.LinkListt;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        LinkListt<Integer> link = new LinkListt<>();
        link.add(10, 0);
        link.add(20, 1);
        link.add(30, 2);
        link.add(40, 3);
        link.add(50, 2);
        System.out.println("插入后: " + link);
        link.remove(2);
        System.out.println("删除后: " + link);
        link.setElement(0, 50);
        System.out.println("更新后: " + link);
        System.out.print("输入查询的节点位置: ");
        int index = input.nextInt();
        System.out.println("查询节点的元素: " + link.getElement(index));
    }
}

• LinkList代码

package ClassStudy;

public class LinkListt<E> {

    private final Node<E> head = new Node<>(null);//链表的头结点，用于连接之后的所有结点
    private int size = 0;   //当前的元素数量还是要存一下，方便后面操作

    private static class Node<E> {  //结点类，仅供内部使用
        E element;   //每个结点都存放元素
        Node<E> next;   //指向下一个结点的引用

        public Node(E element) {//下一节点的元素;通过构造函数赋值
            this.element = element;
        }
    }

    //插入
    public void add(E element, int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("插入位置非法，合法的插入位置为：0 ~ " + size);
        Node<E> prev = head;   //先找到对应位置的前驱结点
        for (int i = 0; i < index; i++)
            prev = prev.next;
        Node<E> node = new Node<>(element);   //创建新的结点
        node.next = prev.next;   //先让新的节点指向原本在这个位置上的结点
        prev.next = node;   //然后让前驱结点指向当前结点
        size++;   //完事之后一样的，更新size
    }

    //删除
    public E remove(int index) {
        if (index < 0 || index > size - 1)   //同样的，先判断位置是否合法
            throw new IndexOutOfBoundsException("删除位置非法，合法的删除位置为：0 ~ " + (size - 1));
        Node<E> prev = head;
        for (int i = 0; i < index; i++)   //同样需要先找到前驱结点
            prev = prev.next;
        E e = prev.next.element;   //先把待删除结点存放的元素取出来
        prev.next = prev.next.next;  //可以删了
        size--;   //记得size--
        return e;
    }

    //更新
    public void setElement(int index, E e) {
        if (index < 0 || index > size - 1)
            throw new IndexOutOfBoundsException("更新位置非法，合法的删除位置为：0 ~ " + (size - 1));
        //获取指定位置的原节点
        Node<E> node = head;
        //同样需要先找到前驱结点
        for (int i = 0; i < index; i++) node = node.next;//需要到达更新节点的前一节点
        node.next.element = e;
    }


    //查询
    public E getElement(int index) {
        if (index < 0 || index > size - 1)
            throw new IndexOutOfBoundsException("非法的位置，合法的位置为：0 ~ " + (size - 1));
        Node<E> node = head;
        while (index-- >= 0)   //这里直接让index减到-1为止
            node = node.next;
        return node.element;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("链表长度: ").append(getSize()).append(" ");

        Node<E> node = head.next;   //从第一个结点开始，一个一个遍历，遍历一个就拼接到字符串上去
        builder.append("链表元素: ").append(" ");
        while (node != null) {
            builder.append(node.element).append(" ");
            node = node.next;
        }
        return builder.toString();
    }
}