Java手写链表

转x33g5p2x  于2021-12-06 转载在 Java  
字(9.2k)|赞(0)|评价(0)|浏览(276)

简单介绍

链表是java数据结构中一种很基础很常见又很重要的数据结构，JDK中许多内置jar包基于单链表实现，比如像我们熟悉的linkedList。
链表的数据结构非常简单，就是一个个节点连接在一起，形成一个完整的链条，每个节点包含2部分，数据域date，和一个指向下一个节点引用的指针next（java中我们叫引用）
如图：

链表的分类有很多种，比如单向链表，双向链表，循环链表等

头插法和尾插法

在链表中插入操作还是比较重要的，因此我先用图示介绍一下这两种插入方式（以单向链表为例）

核心：

newNode.next = head.next;	// 新增节点的next域指向头节点的next节点 
head.next = newNode;		// 头结点的next域再指向新增节点

动画：

尾插法：需要借助一个指针rear，指向当前链表最后一个节点，每次处理rear指针指向的节点和新增的节点的关系即可。

核心：

rear.next = newNode;    // 尾节点的next域指向新节点
rear = newNode;         // 尾指针变成newNode指针

动画：

单向链表

/** * 自定义单向链表 * @param <T> */
static class SingleLinkedList<T> {
    public int size;        // 链表大小
    public Node<T> head = new Node<>();    // 头结点 (先初始化一下)
    public Node<T> rear = head;    // 尾节点 (刚开始指向头结点)
    /** * 数据节点类 * @param <T> */
    private class Node<T> {
        T date;         // date存储数据
        Node<T> next;   // 存储下个节点的引用指针

        public Node(T date) {
            this.date = date;
            this.next = null;
        }

        public Node() {
        }

        @Override
        public String toString() {
            return "Node{" +
                    "date=" + date +
                    '}';
        }
    }
}

注意：

  • 首先定义SingleLinkedList类，这里接收的数据我们用一个<T>泛型来规范。
  • 再定义一个Node节点类，这个相当于一个容器。（如果把SingleLinkedList比喻成整个糖葫芦，那么Node就是糖葫芦上的山楂果）。Node节点需要有两个属性：date用来存储数据，next用来指向下个node节点。
  • 因为是单向链表，因此头结点head是不可缺少的；因为我们是尾插法因此这里最好加一个尾指针rear；同时加个size来记录链表的长度。
/** * 从尾部添加数据 * @param date */
public void addRear(T date) {
    // 根据添加的内容 创建一个新节点 next域为null
    Node<T> newNode = new Node<>(date);
    rear.next = newNode;    // 尾节点的next指向新节点
    rear = newNode;         // 将新节点设置为尾节点
    size++;                 // 链表大小 +1
}
/** * 从头部添加数据 （头插法） * @param date */
public void addHead(T date) {
    // 根据添加的内容 创建一个新节点 next域为null
    Node<T> newNode = new Node<>(date);
    newNode.next = head.next;	// 新增节点的next域指向头节点的next节点
    head.next = newNode;		// 头结点的next域再指向新增节点
    size++;
}
/** * 指定插入到某个位置 * @param date * @param index */
public void insert(T date, int index) {
    if (index > size) {
        System.out.println("下标超出链表大小");
        return;
    }
    Node temp = head;
    for (int i=1; i<=index-1; i++) {    // 找到插入位置的前一个节点 因此是index-1 因为这是单向链表 不能指向前一个节点
        temp = temp.next;
    }
    // 根据添加的内容 创建一个新节点 next域为null
    Node<T> newNode = new Node<>(date);
    // 关键逻辑
    newNode.next = temp.next;
    temp.next = newNode;
    size++;
}
/** * 删除指定下标的节点 * @param index */
public void delete(int index) {
    if (index > size) {
        System.out.println("下标超出链表大小");
        return;
    }
    Node temp = head;
    for (int i=1; i<=index-1; i++) {  // 找到插入位置的前一个节点 因此是index-1 因为这是单向链表 不能指向前一个节点
        temp = temp.next;
    }
    // 主要逻辑
    temp.next = temp.next.next;
    if (index == size) {    // 如果删除的是最后一个节点
        rear = temp;        // 将倒数第二个节点设置为尾节点
    }
    size--;
}
/** * 修改指定下标的元素 * @param date * @param index */
public void update(T date, int index) {
    if (index > size) {
        System.out.println("下标超出链表大小");
        return;
    }
    Node temp = head;
    for (int i=1; i<=index; i++) {  // 注意这里是 index不是index-1 和上面的插入方法是有区别的
        temp = temp.next;
    }
    // 找到指定节点后 直接修改它的date即可
    temp.date = date;
}
/** * 遍历链表 */
public void showList() {
    if (this.size == 0) {
        System.out.println("链表为空！");
        return;
    }
    Node temp = head;   // 因为head不能动 因此这里我们需要添加一个临时指针
    while (true) {
        if (temp == null) break;
        System.out.println(temp);
        temp = temp.next;   // 这点很重要 临时节点后移 （别错写成 temp.next = temp 了）
    }
}
/** * 获取指定下标的节点值 * @param index * @return */
public Object get(int index) {
    if (index > size) {
        System.out.println("下标超出链表大小");
        return -1;
    }
    Node temp = head;
    for (int i=1; i<=index; i++) {
        temp = temp.next;
    }
    return temp.date;
}

测试代码：

SingleLinkedList<String> myList = new SingleLinkedList<>();
myList.addRear("字节跳动");myList.addRear("阿里");myList.addRear("腾讯");myList.addRear("美团");
myList.showList();
System.out.println("链表的大小："+myList.size);

myList.insert("华为",4);
myList.showList();
System.out.println("链表的大小："+myList.size);

myList.update("百度",5);
myList.showList();
System.out.println("链表的大小："+myList.size);

myList.delete(3);
myList.showList();
System.out.println("链表的大小："+myList.size);

System.out.println(myList.get(1));

myList.addHead("上官婉儿");
myList.addHead("橘右京");
myList.addHead("廉颇");
myList.showList();
System.out.println("链表的大小："+myList.size);

输出：

Node{date=null}
Node{date=字节跳动}
Node{date=阿里}
Node{date=腾讯}
Node{date=美团}
链表的大小：4
Node{date=null}
Node{date=字节跳动}
Node{date=阿里}
Node{date=腾讯}
Node{date=华为}
Node{date=美团}
链表的大小：5
Node{date=null}
Node{date=字节跳动}
Node{date=阿里}
Node{date=腾讯}
Node{date=华为}
Node{date=百度}
链表的大小：5
Node{date=null}
Node{date=字节跳动}
Node{date=阿里}
Node{date=华为}
Node{date=百度}
链表的大小：4
字节跳动
Node{date=null}
Node{date=廉颇}
Node{date=橘右京}
Node{date=上官婉儿}
Node{date=字节跳动}
Node{date=阿里}
Node{date=华为}
Node{date=百度}
链表的大小：7

思路
其实很简单。 首先创建一个新的链表，然后遍历之前老的链表，将一个个节点用头插法的方式添加到新的链表中，这里头插法很关键。

代码实现：

/** * 链表反转 */
public void reverse() {
    // 首先创建一个新的临时链表
    SingleLinkedList tempLinkedList = new SingleLinkedList();
    // 开始遍历 从头结点的next节点开始
    Node curNode = this.head.next;
    while (true) {
        if (curNode == null) break;
        // 将当前节点利用 头插法 添加到临时链表中 （头插法是关键）
        tempLinkedList.addHead(curNode.date);
        curNode = curNode.next;
    }
    // 最后把临时链表的head索引赋值给当前链表的head
    this.head = tempLinkedList.head;
}

测试代码：

SingleLinkedList<String> myList = new SingleLinkedList<>();
myList.addRear("字节跳动");myList.addRear("阿里");
myList.addRear("腾讯");myList.addRear("美团");
myList.addRear("华为");
myList.showList();
myList.reverse();
System.out.println("--------------反转后------------");
myList.showList();

输出结果：

Node{date=null}
Node{date=字节跳动}
Node{date=阿里}
Node{date=腾讯}
Node{date=美团}
Node{date=华为}
--------------反转后------------
Node{date=null}
Node{date=华为}
Node{date=美团}
Node{date=腾讯}
Node{date=阿里}
Node{date=字节跳动}

双向链表

其实和单向链表大同小异，区别在于双向链表的Node节点有两个指针，一个指向下一个节点-next，一个指向上一个节点-pre。
其他的增加、删除方法要注意处理next、pre的指向关系

代码实现：

/** * 自定义双向链表 * @param <T> */
static class DoubleLinkedList<T> {
    public int size;        // 链表大小
    public Node<T> head = new Node();    // 头结点 (先初始化一下)
    public Node<T> rear = head;    // 尾节点 (刚开始指向头结点)

    /** * 从尾部添加数据 （尾插法） * @param date */
    public void addRear(T date) {
        // 根据添加的内容 创建一个新节点 next域为null
        Node<T> newNode = new Node(date);
        rear.next = newNode;    // 尾节点的next域指向新节点
        newNode.pre = rear;     // 新节点的pre域执行尾节点
        rear = newNode;         // 将新添加的节点设置为尾节点
        size++;                 // 链表大小 +1
    }

    /** * 从头部添加数据 （头插法） * @param date */
    public void addHead(T date) {
        // 根据添加的内容 创建一个新节点 next域为null
        Node<T> newNode = new Node(date);
        // 主要逻辑
        newNode.next = head.next;
        head.next.pre = newNode;
        head.next = newNode;
        newNode.pre = head;
        size++;
    }

    /** * 删除指定下标的节点 * @param index */
    public void delete(int index) {
        if (index > size) {
            System.out.println("下标超出链表大小");
            return;
        }
        Node temp = head;
        for (int i=1; i<=index; i++) {  // 找到对应下标的节点
            temp = temp.next;
        }
        // 主要逻辑
        if (index < size) { // 要删除的节点不是最后一个节点
            temp.pre.next = temp.next;
            temp.next.pre = temp.pre;
        }else { // 要删除的节点是最后一个节点
            rear = temp.pre;        // 将倒数第二个节点设置为尾节点
            temp.pre.next = null;  // 然后将倒数第二个节点的next指向为null即可

        }
        size--;
    }

	/** * 修改指定下标的节点 * @param date * @param index */
    public void update(T date, int index) {
        if (index > size) {
            System.out.println("下标超出链表大小");
            return;
        }
        Node temp = head;
        for (int i=1; i<=index; i++) {
            temp = temp.next;
        }
        // 找到指定节点后 直接修改它的date即可
        temp.date = date;
    }

    /** * 遍历链表 */
    public void showList() {
        if (this.size == 0) {
            System.out.println("链表为空！");
            return;
        }
        Node temp = head;   // 因为head不能动 因此这里我们需要添加一个临时指针
        while (true) {
            if (temp == null) break;
            System.out.println(temp);
            temp = temp.next;   // 这点很重要 临时节点后移 （别错写成 temp.next = temp 了）
        }
    }

    /** * 数据节点类 * @param <T> */
    private class Node<T> {
        T date;         // date存储数据
        Node<T> next;   // 指向下一个节点
        Node<T> pre;    // 指向上一个节点

        public Node(T date) {
            this.date = date;
            this.next = null;
            this.pre = null;
        }

        public Node() {
        }

        @Override
        public String toString() {
            return "Node{" +
                    "date=" + date +
                    '}';
        }
    }
}

测试代码：

DoubleLinkedList<Object> myDoublelinkedList = new DoubleLinkedList<>();
myDoublelinkedList.addRear("华为");myDoublelinkedList.addRear("腾讯");
myDoublelinkedList.addHead("字节跳动");myDoublelinkedList.addHead("百度");
myDoublelinkedList.delete(4);
myDoublelinkedList.addRear("阿里");
myDoublelinkedList.showList();

输出结果：

Node{date=null}
Node{date=百度}
Node{date=字节跳动}
Node{date=华为}
Node{date=阿里}

循环链表

其实和单向链表差不多，只是在每次添加的时候，新增节点的next域要指向head节点

/** * 自定义单向环形列表 * @param <T> */
static class CirculSingleLinkedList<T> {
    public int size;        // 链表大小
    public Node<T> head = null;    // 头结点
    public Node<T> rear = null;    // 尾节点

    public void add(String data) {
        // 根据添加的内容 创建一个新节点 next域为null
        Node<T> newNode = new Node(data);
        if (size == 0) {        // 插入第一个节点
            head = newNode;
            rear = newNode;
            rear.next = head;   // 也就是自己指向自己
            size++;
            return;
        }
        rear.next = newNode;    // 尾节点的next域指向新节点
        rear = newNode;         // 新增节点设置成尾节点
        rear.next = head;       // 将尾节点的next域指向头节点
        size++;                 // 链表大小 +1
    }

    /** * 从循环链表中去除某个节点 * @param name */
    public void remove(String name) {
        Node temp = head;
        while (true) {
            if (name.equals(temp.next.data)) { // 找到了那个节点 就是temp.next
                if (temp.next == head) {  // 如果移除的节点是头结点
                    head = temp.next.next;  // 将头结点的下个节点设置成新的头结点
                }
                if (temp.next == rear) {  // 如果移除的节点是尾结点
                    rear = temp;  // 将尾结点的上个节点设置成新的尾结点
                }
                temp.next = temp.next.next; // 移除节点
                System.out.println("移除节点："+name);
                size--;
                break;
            }
            temp = temp.next;               // 节点后移
            if (temp == head) {             // 如果temp节点又变为head说明 走了一个循环还没找到要删除的节点 说明不存在
                System.out.println("不存在该节点");
                return;
            }
        }
    }

    public void showList() {
        if (this.size == 0) {
            System.out.println("链表为空！");
            return;
        }
        Node temp = head;
        System.out.print(temp.data+" -> ");
        while (true) {
            temp = temp.next;
            if (temp == head) break;
            System.out.print(temp.data+" -> ");
        }
    }

    /** * 数据节点类 * @param <T> */
    private class Node<T> {
        T data;         // data存储数据
        Node<T> next;   // 存储下个节点的引用指针

        public Node(T data) {
            this.data = data;
            this.next = null;
        }

        public Node() {
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }
}

测试代码：

CirculSingleLinkedList list = new CirculSingleLinkedList<String>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
list.add("6");
list.add("7");
list.remove("1");
list.remove("7");
list.remove("4");
list.showList();

输出结果：

移除节点：1
移除节点：7
移除节点：4
2 -> 3 -> 5 -> 6 ->

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/qq_45464560/article/details/120454259

内容来源于网络，如有侵权，请联系作者删除！

Java数据结构链表

相关文章

    查看更多
    微信公众号

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com