图标
创作项目友邻自述归档留言

Java链表实现

转换阵营 ing,大部分的介绍都在注释写了,这里就不再重复了,注释中没有关于链表的原理,如果还不懂链表的可以先去看其他教程,这里不写主要是我比较懒( ̄ ▽  ̄)"

之前的算法有问题,现在已经修改完成,并重写了部分代码,对数据域使用泛型,可以存放任何对象了,存放不同数据类型时就不再需要定义多个链表类了ヾ(≧▽≦*)o

这个算法还有优化的空间,不久后将升级,心急的可以看 C 链表重置版然后将其改成 Java 即可

package MyLinkedListDemo;

import java.util.Scanner;

public class MyLinkedListDemo {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        MyLinkedList<Integer> list = new MyLinkedList<Integer>();
        list.add(-1, 1);
        list.add(-1, 2);
        list.add(-1, 3);
        list.add(-1, 4);
        list.add(-1, 5);
        int a = list.get(2);
        System.out.println(a);
        in.close();
        }
    }

    class MyLinkedList<T> {

        //链表总长度
        int len = 0;
        // 头节点
        Node head = null;
        // 尾节点
        Node end = null;

        // 链表节点类(内部类)
        class Node {
            // 上一个节点
            Node prev;
            // 下一个节点
            Node next;
            // 数据块
            T data;

            // 空构造器,用于构造临时节点和定位节点等不需要使用数据块的节点
            Node() {
            };

            // 可填入数据的构造器,用填入数据
            Node(T data) {
                // 填入数据到数据块
                this.data = data;
            }
        }

        // 插入链表节点的方法
        // 参数i : 表示要插入的位置,当 i = -1 时新节点会被放置头位置,若 i = -2 时新节点会被放置至尾位置
        public void add(int i /* 要添加的位置,新节点会添加至该位置之后 */, T data /* 传入数据 */) {
            // 递增定位
            len++;
            int j;
            // 定义定位节点
            Node indexNode = head;
            // 创建新节点
            Node newNode = new Node(data);

            // 判断链表是否为空
            if (head == null) {
                // 若是只需将新节点设为头节点和尾节点就行
                head = newNode;
                end = newNode;
                return;
            }

            // Create Mode
            if (i == -1) // 头插法
            {
                newNode.next = head;
                head.prev = newNode;
                head = newNode;
                return;
            } else if (i == -2) // 尾插法
            {
                while (indexNode.next != null) {
                    indexNode = indexNode.next;
                }
            }

            // Insert Mode

            // 移动定位节点至指定位置
            for (j = 0; j < i && indexNode != null; j++) {
                indexNode = indexNode.next;
            }
            // 判断是否是添加至最后一个节点
            if (indexNode.next == null) {
                // 将上一个节点next指向新节点
                indexNode.next = newNode;
                // 将新节点的prev指向上一个节点
                newNode.prev = indexNode;
                // 将新节点的next指向null
                newNode.next = null;
                // 将新节点设为尾节点
                end = newNode;
                return;
            }
            // 创建临时节点用于存储原下一个节点的地址
            Node tempNode = indexNode.next;
            // 将上一个节点的next指向新节点
            indexNode.next = newNode;
            // 将新节点的next指向原下一个节点
            newNode.next = tempNode;
            // 将新节点的prev指向上一个节点
            newNode.prev = indexNode;
            // 将原下一个节点的prev指向新节点
            tempNode.prev = newNode;
        }

        // 插入带数据的链表到指定位置,操作方式同add,只是新增的节点是已经有数据的
        public void add(int i, Node haveNode) {
            len++;
            int j;
            Node indexNode = head;

            if (i == -1) {
                haveNode.next = head;
                head.prev = haveNode;
                head = haveNode;
                return;
            }

            for (j = 0; j < i && indexNode != null; j++) {
                indexNode = indexNode.next;
            }

            if (indexNode.next == null) {
                indexNode.next = haveNode;
                haveNode.prev = indexNode;
                haveNode.next = null;
                end = haveNode;
                return;
            }

            haveNode.next = indexNode.next;
            haveNode.next.prev = haveNode;
            haveNode.prev = indexNode;
            indexNode.next = haveNode;
        }

        // 删除指定节点
        // 参数 i : 当 i = 0 时代表删除第一个节点,i = -1 时代表删除最后一个节点
        public void delete(int i/* 要删除节点的位置 */) {
            len--;
            // 判断是否是删除第一个节点
            if (i == 0) {
                // 将头节点指向第二个节点,然后将头节点的prev设置为null,这样就屏蔽掉了第一个节点
                head = head.next;
                head.prev = null;
                return;
            }
            // 若是删除最后一个节点,那只需将尾节点移到倒数第二个节点即可
            else if (i == -1) {
                end = end.prev;
                end.next = null;
                return;
            }

            // 递增定位
            int j;
            // 创建定位节点,将其指向头节点
            Node indexNode = head;
            // 将定位节点移至要删除节点的上一个节点
            for (j = 0; j < i - 1 && indexNode != null; j++) {
                indexNode = indexNode.next;
            }
            // 判断要删除节点是否是最后一个节点
            if (indexNode.next.next == null) {
                // 操作方式同删除头节点与
                end = end.prev;
                end.next = null;
                return;
            }
            // 要删除节点的下一个节点prev设置为要删除节点的上一个节点
            indexNode.next.next.prev = indexNode;
            // 将要删除节点的上一个节点的next设置为要删除节点的下一个节点
            indexNode.next = indexNode.next.next;
        }

        // 清空链表
        public void clear() {
            len = 0;
            // 清空链表只需将头节点和尾节点设置为null即可,内存会由垃圾回收器回收
            head = null;
            end = null;
        }

        // 遍历输出链表数据
        public void print() {
            // 创建定位节点
            Node indexNode = head;
            // 使用while循环进行遍历
            while (indexNode != null) {
                // 输出数据
                System.out.print(indexNode.data.toString() + " ");
                // 移动定位节点
                indexNode = indexNode.next;
            }
            // 换行
            System.out.println();
        }

        // 链表逆置
        public void resever() {
            // 创建临时节点用来临时存储指向数据
            Node tempNode = new Node();
            // 将头节点与尾节点交换
            tempNode = head;
            head = end;
            end = tempNode;
            // 创建定位节点
            Node indexNode = head;
            // 循环交换next和prev数据
            while (indexNode.prev != null && (indexNode.next != null || indexNode == head)) {
                tempNode = indexNode.next;
                indexNode.next = indexNode.prev;
                indexNode.prev = tempNode;
                indexNode = indexNode.next;
            }
            // 设置最后一个节点的next为null
            end.next = null;
            // 设置最后一个节点的prev数据
            end.prev = tempNode.next;
        }

        // 添加新节点到列表末尾
        public void addFirst(T data) {
            this.add(-2, data);
        }

        // 添加新节点到列表头
        public void addLast(T data) {
            this.add(-1, data);
        }

        // 获取指定位置的数据
        public T get(int i) {
            Node indexNode = head;
            for (int j = 0; j < i; j++) {
                indexNode = indexNode.next;
            }
            return indexNode.data;
        }

    }
package MyLinkedListDemo;

import java.util.Scanner;

public class MyLinkedListDemo {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        MyLinkedList<Integer> list = new MyLinkedList<Integer>();
        list.add(-1, 1);
        list.add(-1, 2);
        list.add(-1, 3);
        list.add(-1, 4);
        list.add(-1, 5);
        int a = list.get(2);
        System.out.println(a);
        in.close();
        }
    }

    class MyLinkedList<T> {

        //链表总长度
        int len = 0;
        // 头节点
        Node head = null;
        // 尾节点
        Node end = null;

        // 链表节点类(内部类)
        class Node {
            // 上一个节点
            Node prev;
            // 下一个节点
            Node next;
            // 数据块
            T data;

            // 空构造器,用于构造临时节点和定位节点等不需要使用数据块的节点
            Node() {
            };

            // 可填入数据的构造器,用填入数据
            Node(T data) {
                // 填入数据到数据块
                this.data = data;
            }
        }

        // 插入链表节点的方法
        // 参数i : 表示要插入的位置,当 i = -1 时新节点会被放置头位置,若 i = -2 时新节点会被放置至尾位置
        public void add(int i /* 要添加的位置,新节点会添加至该位置之后 */, T data /* 传入数据 */) {
            // 递增定位
            len++;
            int j;
            // 定义定位节点
            Node indexNode = head;
            // 创建新节点
            Node newNode = new Node(data);

            // 判断链表是否为空
            if (head == null) {
                // 若是只需将新节点设为头节点和尾节点就行
                head = newNode;
                end = newNode;
                return;
            }

            // Create Mode
            if (i == -1) // 头插法
            {
                newNode.next = head;
                head.prev = newNode;
                head = newNode;
                return;
            } else if (i == -2) // 尾插法
            {
                while (indexNode.next != null) {
                    indexNode = indexNode.next;
                }
            }

            // Insert Mode

            // 移动定位节点至指定位置
            for (j = 0; j < i && indexNode != null; j++) {
                indexNode = indexNode.next;
            }
            // 判断是否是添加至最后一个节点
            if (indexNode.next == null) {
                // 将上一个节点next指向新节点
                indexNode.next = newNode;
                // 将新节点的prev指向上一个节点
                newNode.prev = indexNode;
                // 将新节点的next指向null
                newNode.next = null;
                // 将新节点设为尾节点
                end = newNode;
                return;
            }
            // 创建临时节点用于存储原下一个节点的地址
            Node tempNode = indexNode.next;
            // 将上一个节点的next指向新节点
            indexNode.next = newNode;
            // 将新节点的next指向原下一个节点
            newNode.next = tempNode;
            // 将新节点的prev指向上一个节点
            newNode.prev = indexNode;
            // 将原下一个节点的prev指向新节点
            tempNode.prev = newNode;
        }

        // 插入带数据的链表到指定位置,操作方式同add,只是新增的节点是已经有数据的
        public void add(int i, Node haveNode) {
            len++;
            int j;
            Node indexNode = head;

            if (i == -1) {
                haveNode.next = head;
                head.prev = haveNode;
                head = haveNode;
                return;
            }

            for (j = 0; j < i && indexNode != null; j++) {
                indexNode = indexNode.next;
            }

            if (indexNode.next == null) {
                indexNode.next = haveNode;
                haveNode.prev = indexNode;
                haveNode.next = null;
                end = haveNode;
                return;
            }

            haveNode.next = indexNode.next;
            haveNode.next.prev = haveNode;
            haveNode.prev = indexNode;
            indexNode.next = haveNode;
        }

        // 删除指定节点
        // 参数 i : 当 i = 0 时代表删除第一个节点,i = -1 时代表删除最后一个节点
        public void delete(int i/* 要删除节点的位置 */) {
            len--;
            // 判断是否是删除第一个节点
            if (i == 0) {
                // 将头节点指向第二个节点,然后将头节点的prev设置为null,这样就屏蔽掉了第一个节点
                head = head.next;
                head.prev = null;
                return;
            }
            // 若是删除最后一个节点,那只需将尾节点移到倒数第二个节点即可
            else if (i == -1) {
                end = end.prev;
                end.next = null;
                return;
            }

            // 递增定位
            int j;
            // 创建定位节点,将其指向头节点
            Node indexNode = head;
            // 将定位节点移至要删除节点的上一个节点
            for (j = 0; j < i - 1 && indexNode != null; j++) {
                indexNode = indexNode.next;
            }
            // 判断要删除节点是否是最后一个节点
            if (indexNode.next.next == null) {
                // 操作方式同删除头节点与
                end = end.prev;
                end.next = null;
                return;
            }
            // 要删除节点的下一个节点prev设置为要删除节点的上一个节点
            indexNode.next.next.prev = indexNode;
            // 将要删除节点的上一个节点的next设置为要删除节点的下一个节点
            indexNode.next = indexNode.next.next;
        }

        // 清空链表
        public void clear() {
            len = 0;
            // 清空链表只需将头节点和尾节点设置为null即可,内存会由垃圾回收器回收
            head = null;
            end = null;
        }

        // 遍历输出链表数据
        public void print() {
            // 创建定位节点
            Node indexNode = head;
            // 使用while循环进行遍历
            while (indexNode != null) {
                // 输出数据
                System.out.print(indexNode.data.toString() + " ");
                // 移动定位节点
                indexNode = indexNode.next;
            }
            // 换行
            System.out.println();
        }

        // 链表逆置
        public void resever() {
            // 创建临时节点用来临时存储指向数据
            Node tempNode = new Node();
            // 将头节点与尾节点交换
            tempNode = head;
            head = end;
            end = tempNode;
            // 创建定位节点
            Node indexNode = head;
            // 循环交换next和prev数据
            while (indexNode.prev != null && (indexNode.next != null || indexNode == head)) {
                tempNode = indexNode.next;
                indexNode.next = indexNode.prev;
                indexNode.prev = tempNode;
                indexNode = indexNode.next;
            }
            // 设置最后一个节点的next为null
            end.next = null;
            // 设置最后一个节点的prev数据
            end.prev = tempNode.next;
        }

        // 添加新节点到列表末尾
        public void addFirst(T data) {
            this.add(-2, data);
        }

        // 添加新节点到列表头
        public void addLast(T data) {
            this.add(-1, data);
        }

        // 获取指定位置的数据
        public T get(int i) {
            Node indexNode = head;
            for (int j = 0; j < i; j++) {
                indexNode = indexNode.next;
            }
            return indexNode.data;
        }

    }

Java链表实现

https://blog.ixk.me/post/java-linked-list-implementation
  • 许可协议

    BY-NC-SA

  • 本文作者

    Otstar Lin

  • 发布于

    2018/11/29

转载或引用本文时请遵守许可协议,注明出处、不得用于商业用途!

图的搜索(遍历) - BFS & DFSC 快速排序