[数据结构与算法]轻松拿捏链表(java)

链表

顺序表的缺陷

上篇文章我们介绍了顺序表,顺序表的底层是数组，当我们在进行数组的添加和删除时，需要将后序元素依次移动位置，使得时间复杂度为O(N),效率比较低。因此:java引进了LinkedList，即链表结构。

概念

链表是一种物理存储结构上非连续的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。简单来说，链表不会按照顺序表的存储结构去存储数据，而是在每一个节点里存放下个节点的地址 。

结构

这是一个简单的单向链表的结点，val表示的是当前结点要存的值，next表示引用，用来存放下一个结点的地址。

由于Java中不存在指针，所以每一个结点通常为一个类，而next是一个结点类实例的引用

创建链表

我们介绍了链表，可是该如何创建一个链表呢？

在Java中我们用类来表示链表的结构

public static class Node {
    int value;//值
    Node next;//结点引用，引用当前节点的下一节点
    public Node(int value) {
        this.value = value;
    }
}

结点的插入

在链表中插入一个节点时，一般有3种方法：头插、尾插、指定位置插入

头插

在链表的起始位置插入结点。

public void addFirst(int data) {
    Node node = new Node(data);
    node.next = head;
    head = node;
}

代码很简单，思路也很简单

尾插

与头插相似，只是在最后一个结点的位置插入新结点。

//尾插法
public void addLast(int data) {
    //创建新链表
    Node node = new Node(data);
    //判断链表是否为空
    if (head == null) {
        addFirst(data);
        return;
    }
    //后面节点
    Node current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = node;
}

指定位置插入

private void checkRange(int index) {
    if (index < 0 || index > size()) {
        throw new IndexOutOfBoundsException("下标非法 i=" + index);
    }
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) {
    //检查index合法性
    checkRange(index);
    //首位
    if (index == 0) {
        addFirst(data);
        return;
    }
    //尾部
    if (index == size()) {
        addLast(data);
        return;
    }
    //中间位置
    //首先找到所找节点的上一节点
    Node preNode = findPreNode(index);
    //创建新节点
    Node node = new Node(data);
    //用node.next引用preNode.next
    node.next = preNode.next;
    //preNode.next引用新节点
    preNode.next = node;
}
private Node findPreNode(int index) {
    //创建临时节点
    Node current = head;
    for (int i = 0; i < (index - 1); i++) {
        current = current.next;
    }
    return current;
}

查找是否包含关键字key是否在单链表当中

遍历数组即可

public boolean contains(int key) {
    //遍历链表
    Node current = head;
    while (current != null) {
        if (current.value == key) {
            return true;
        }
        current = current.next;
    }
    return false;

删除元素

这个会出现2种情况：删除第一次出现的关键字key和删除出现的所有关键字key

删除第一次出现的关键字key

public void remove(int key) {
    //若为头节点
    if (head.value == key) {
        head = head.next;
        return;
    }
    //不是头节点
    Node current = head;
    while (current != null) {
        if (current.next.value == key) {
            current.next = current.next.next;
            return;
        }
        current = current.next;
    }
}

删除出现的所有关键字key

public void removeAllKey(int key) {
    //判断链表是否为空
    if (head == null) {
        return;
    }
    //出现在首位
    if (head.value == key) {
        head = head.next;
    }
    //不为空
    //两个临时变量
    Node current = head.next;
    Node prev = head;
    while (current != null) {
        if (current.value == key) {
            prev.next = current.next;
        } else {
            prev = current;
        }
        current = current.next;
    }
}

获取链表长度

public int size() {
    //遍历每个节点，统计节点个数
    Node current = head;
    int count = 0;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}

清空链表

public void clear() {
    //手动将每个节点置空
    Node current = head;
    while (current != null) {
        //得到下一个节点
        Node nextNode = current.next;
        current.next = null;
        current = nextNode;
    }
    //最简便方法
    head = null;
}

链表打印

public void display() {
    //创建一个临时变量引用head
    Node current = head;
    StringBuilder sb = new StringBuilder();
    sb.append("[");
    while (current != null) {
        sb.append(current.value);
        //最后一个节点不加空格
        if (current.next != null) {
            sb.append(" ");
        }
        current = current.next;
    }
    sb.append("]");
    System.out.println(sb.toString());
}

以上就是链表的基本操作了，下面是全部源码

import java.util.Stack;

public class SingleLinkedList {
    public static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public Node head;

    //头插法
    public void addFirst(int data) {
        Node node = new Node(data);
        node.next = head;
        head = node;

    }

    //尾插法
    public void addLast(int data) {
        //创建新链表
        Node node = new Node(data);
        //判断链表是否为空
        if (head == null) {
            addFirst(data);
            return;
        }
        //后面节点
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = node;
    }

    private void checkRange(int index) {
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException("下标非法 i=" + index);
        }
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        //检查index合法性
        checkRange(index);

        //首位
        if (index == 0) {
            addFirst(data);
            return;
        }
        //尾部
        if (index == size()) {
            addLast(data);
            return;
        }
        //中间位置
        //首先找到所找节点的上一节点
        Node preNode = findPreNode(index);
        //创建新节点
        Node node = new Node(data);
        //用node.next引用preNode.next
        node.next = preNode.next;
        //preNode.next引用新节点
        preNode.next = node;
    }

    private Node findPreNode(int index) {
        //创建临时节点
        Node current = head;
        for (int i = 0; i < (index - 1); i++) {
            current = current.next;
        }
        return current;
    }


    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        //遍历链表
        Node current = head;
        while (current != null) {
            if (current.value == key) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        //若为头节点
        if (head.value == key) {
            head = head.next;
            return;
        }
        //不是头节点
        Node current = head;
        while (current != null) {
            if (current.next.value == key) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        //判断链表是否为空
        if (head == null) {
            return;
        }
        //出现在首位
        if (head.value == key) {
            head = head.next;
        }
        //不为空
        //两个临时变量
        Node current = head.next;
        Node prev = head;
        while (current != null) {
            if (current.value == key) {
                prev.next = current.next;
            } else {
                prev = current;
            }
            current = current.next;
        }
    }

    //得到单链表的长度
    public int size() {
        //遍历每个节点，统计节点个数
        Node current = head;
        int count = 0;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

    public void clear() {

        //手动将每个节点置空
        Node current = head;
        while (current != null) {
            //得到下一个节点
            Node nextNode = current.next;
            current.next = null;
            current = nextNode;
        }

        //最简便方法
        head = null;
    }

    public void display() {
        //创建一个临时变量引用head
        Node current = head;
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while (current != null) {
            sb.append(current.value);
            //最后一个节点不加空格
            if (current.next != null) {
                sb.append(" ");
            }
            current = current.next;
        }
        sb.append("]");
        System.out.println(sb.toString());
        /*while(current!=null){
            System.out.print(current.value+" ");
            current=current.next;
        }
        System.out.println();*/
    }

    public void printList() {
        if (head == null) {
            System.out.println("");
            return;
        }
        Stack<Node> stack = new Stack<>();
        Node current = head;
        while (current != null){
            stack.push(current);
            current=current.next;
        }
        while(!stack.empty()){
            System.out.print(stack.pop().value+" ");
        }
        System.out.println();
    }
}

无头单向链表介绍完了，其他链表后续再写，期待我后面的文章吧。如果有什么问题以及建议，欢迎大家评论和私信，谢谢支持！！！