Java数据结构之链表-单向链表

逃离我推掉我的手 2022-02-13 07:55 342阅读 0赞

**链表**（Linked list）

是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

**单向链表：**

**       **单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。

**链表的操作：**

插入：将新的节点插入到指定的节点后面，如果链表的头结点为空，直接将当前节点设置为头结点; 如果不为空，则将当前节点的下一个节点指向指定节点的下一个节点，指定节点的下一个节点就更新为当前节点；这样我们就完成了节点的插入操作

删除：查询删除的节点的上一个节点，将上一个节点的下一个节点指向当前节点的下一个节点，这样就完成了删除操作

查询：循环节点，每循环一次，更新当前节点为当前节点的下一个节点，直到当前节点为空，如果是第一次循环，当前节点指向头结点；直到寻找到节点信息与我们要查询一致的节点或者当前节点为空时；如果找到则返回当前节点，否则返回null

示例：

单向列表：

/**
     * Created by Administrator on 2019/4/27.
     * 单向链表
     */
    public class SingleLinkedList {
        private int size;//链表节点的个数
        private Node head;//链表的头结点
    
        /**
         * 链表节点
         */
        private class Node {
            private Object data;//节点信息
            private Node next;//下一个节点
    
            public Node(Object data) {
                this.data = data;
            }
        }
    
        /**
         * 创建节点
         *
         * @param obj
         * @return
         */
        public Node createNode(Object obj) {
            return new Node(obj);
        }
    
    
        /**
         * 插入节点
         *
         * @param obj  被选中的节点
         * @param node 节点数据
         * @return
         */
        public Object insert(Object obj, Node node) {
            if (obj == null) {//插入头节点
                this.head = node;
            } else {
                Node selectNode = search(obj);
                if (null == selectNode) {
                    System.out.println("被选中的节点不存在!");
                    return null;
                }
                node.next = selectNode.next;
                selectNode.next = node;
            }
            size++;
            return obj;
        }
        
        /**
         * 根据节点信息删除节点
         *
         * @param obj
         * @return
         */
        public Node delNodeByObj(Object obj) {
            if (isEmpty()) {
                System.out.println("链表为空!");
                return null;
            }
            Node previousNode = null;
            Node currentNode = search(obj);
            if (null == currentNode) {
                System.out.println("要删除的节点不存在!");
                return null;
            }
            Node node = head;
            while (null != node.next) {
                if (node.next.data.equals(obj)) {
                    previousNode = node;
                    break;
                }
                node = node.next;
            }
            if (null == previousNode) { //previousNode 为null 代表要删除的节点是原头结点 将原头节点的下一个节点作为新的头结点
                head = currentNode.next;
                return currentNode;
            }
            previousNode.next = currentNode.next;
            size--;
            return currentNode;
        }
    
        /**
         * 判断节点是否为空
         *
         * @return
         */
        public boolean isEmpty() {
            return size == 0;
        }
    
        /**
         * 根据节点信息获取节点
         *
         * @param obj
         * @return
         */
        public Node search(Object obj) {
            if (isEmpty()) {
                System.out.println("链表为空!");
                return null;
            }
            Node node = head;
            while (null != node) {
                if (node.data.equals(obj)) {
                    return node;
                }
                node = node.next;
            }
            return null;
        }
        
        /**
         * 显示节点信息
         */
        public void display() {
            Node node = head;
            System.out.print("[");
            while (null != node) {
                if (null != node.next)
                    System.out.print(node.data + "->");
                else
                    System.out.print(node.data + "");
                node = node.next;
            }
            System.out.println("]");
        }
    }

测试：

public class Main {
    
        public static void main(String[] args) {
            Main.testSingleLinkedList();
        }
        
        private static void testSingleLinkedList(){
            SingleLinkedList linkedList = new SingleLinkedList();
            linkedList.display();//打印
            linkedList.insert(null, linkedList.createNode("A"));
            linkedList.insert("A", linkedList.createNode("B"));
            linkedList.insert("B", linkedList.createNode("C"));
            linkedList.insert("C", linkedList.createNode("D"));
            linkedList.insert("D", linkedList.createNode("E"));
            linkedList.display();
            linkedList.insert("A", linkedList.createNode("A1"));
            linkedList.display();
            linkedList.delNodeByObj("A");
            linkedList.display();
        }
    }

输出：

[]
    [A->B->C->D->E]
    [A->A1->B->C->D->E]
    [A1->B->C->D->E]