欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java实现单链表的操作

程序员文章站 2022-06-16 13:05:44
本文实例为大家分享了java实现单链表的基本操作,供大家参考,具体内容如下顺序表:物理上逻辑上都连续;链表:物理上不一定连续,逻辑上一定连续的。链表的概念及结构概念:连表示一种物理存储结构上非连续、非...

本文实例为大家分享了java实现单链表的基本操作,供大家参考,具体内容如下

顺序表:物理上逻辑上都连续;
链表:物理上不一定连续,逻辑上一定连续的。

链表的概念及结构

概念:连表示一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是用过链表中的引用链接次序实现的。

8种链表结构:

单项、双向
带头、不带头
循环、非循环

主要的三种链表:

无头单项非循环链表、带头循环单链表、不带头双向循环链表

Java实现单链表的操作

代码实现

1. 接口定义

package com.github.linked.impl;

public interface ilinked {
    // 头插法
    void addfirst(int data);

    // 尾插法
    void addlast(int data);

    // 任意位置插入,第一数据节点为0号下标
    boolean addindex(int index, int data);

    // 查找是否包含关键字 key 在单链表中
    boolean contains(int key);

    // 删除第一次出现的关键字为 key 的节点
    int remove(int key);

    // 删除所有值为 key 的节点
    void removeallkey(int key);

    // 得到单链表的长度
    int getlength();

    // 打印单链表
    void display();

    // 清空单链表以防内存泄漏
    void clear();
}

2. 代码实现接口

package com.github.linked.impl;

public class singlelisted implements ilinked {

    // 节点类
    class node {
        private int data;
        private node next;

        public node(int data) {
            this.data = data;
            this.next = next;
        }
    }

    private node head; //头节点
    public singlelisted() {
        this.head = head;
    }

    /**
     * 头插法
     * @param data 要插入的数据
     */
    @override
    public void addfirst(int data) {
        // 1. 拿到一个实体
        node node = new node(data);

        // 2. 插入
        // 如果是第一次插入,直接到头节点
        if (this.head == null) {
            this.head = node;
        } else { //不是第一次插入
            node.next = this.head; // 插入的节点指向头节点
            this.head = node;      // 更新头节点
        }
    }

    /**
     * 尾插法
     * @param data 要插入的数据
     */
    @override
    public void addlast(int data) {
        // 1. 拿到一个实体
        node node = new node(data);
        node cur = this.head;

        // 2. 插入
        // 如果是第一次插入,直接到头节点
        if (this.head == null) {
            this.head = node;
        } else {
            // 找尾巴
            while (cur.next != null) {
                cur = cur.next;
            }
            // 退出上面的循环,cur所执行的位置就是尾节点
            cur.next = node;
        }
    }

    // 检测 index 该下标是否合法
    private void checkindex(int index) {
        if (index < 0 || index > getlength())
            throw new indexoutofboundsexception("下标不合法!");
    }

    // 找到下标为 index-1 位置的节点
    private node searchindex(int index) {
        checkindex(index);
        if (index == 0)
            return null;
        int count = 0; // 记录行走的步数
        node cur = this.head;

        while (cur.next != null && count < index-1) {
            cur = cur.next;
            count++;
        }

        return cur;
    }

    /**
     * 任意位置插入,第一数据节点为 0号下标
     * @param index 插入的下标
     * @param data 要插入的数据
     * @return true
     */
    @override
    public boolean addindex(int index, int data) {
        node node = new node(data);
        node cur = searchindex(index);

        // 如果链表为空,直接插入到头节点
        if (cur == null) {
            node.next = this.head;
            this.head = node;
        } else { // 链表不为空,插入到 cur 的位置处
            node.next = cur.next;  // 将node链接到cur的下一个节点
            cur.next = node;       // 再将cur链接到node
        }

        return true;
    }

    /**
     * 查找是否包含关键字 key 在单链表中
     * @param key 要查找的关键字
     * @return 找到key返回true,否则返回false
     */
    @override
    public boolean contains(int key) {
        node cur = this.head;
        while (cur != null) {
            if (cur.data == key) {
                return true;
            }
            cur = cur.next;
        }

        return false;
    }

    // 找第一次出现的关键字为 key 的节点的前驱
    private node searchpre(int key) {
        // 1. 是不是第一个节点 if(head,data == key)
        node pre = this.head;
        if (pre.data == key) {
            // 或者 return null;
            return this.head;
        }

        // 2. if(cur.next.data == key)
        while (pre.next != null) {
            if (pre.next.data == key) {
                return pre;
            }
            pre = pre.next;
        }

        return null;
    }

    /**
     * 删除第一次出现的关键字为 key 的节点
     * @param key 要删除的关键字
     * @return olddata
     */
    @override
    public int remove(int key) {
        int olddata = 0;
        node pre = searchpre(key);

        // 1. 若没有找到
        if (pre == null) {
            // return -1;
            throw new unsupportedoperationexception("没有key的前驱");
        }

        // 2. 找到了,并且在第一个节点
        if (pre == this.head && pre.data == key){
            olddata = this.head.data;
            this.head = this.head.next;
            return olddata;
        }

        // 3. 找到了,并且不在第一个节点
        node delnode = pre.next; // 确定要删除的节点的位置
        pre.next = delnode.next; // 让要删除的节点的前驱指向要删除的节点的后一个节点,进而删除该节点

        return 0;
    }

    /**
     * 删除所有值为 key 的节点
     * @param key 要删除的节点的值
     */
    @override
    public void removeallkey(int key) {
        node pre = this.head;
        node cur = this.head.next;

        // 遍历一遍链表
        while (cur != null) {
            // 若找到了关键字,进行删除
            if (cur.data == key) {
                pre.next = cur.next;
                cur = cur.next;
            } else { // 若不是关键字,继续查看链表的下一个
                pre = cur;
                cur = cur.next;
            }
            if (this.head.data == key) {
                this.head = this.head.next;
            }
        }
    }

    /**
     * 得到单链表的长度
     * @return 单链表长度
     */
    @override
    public int getlength() {
        node cur = this.head;
        int count = 0;  // 节点的个数
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 打印单链表
     */
    @override
    public void display() {
        node cur = this.head;
        while (cur != null) {
            system.out.print(cur.data + " ");
            cur = cur.next;
        }
        system.out.println();
    }

    /**
     * 清空单链表以防内存泄漏
     */
    @override
    public void clear() {
        while (this.head != null) {
            node cur = this.head.next;
            this.head.next = null;
            this.head = cur;
        }
    }
}

3. 测试代码

package com.github.linked.impl;

public class testdemo {
    public static void main(string[] args) {

        //mysinglelistimpl mysinglelist = new mysinglelistimpl();
        singlelisted mysinglelist = new singlelisted();

        mysinglelist.addfirst(10);
        mysinglelist.addfirst(20);
        mysinglelist.addfirst(30);
        mysinglelist.addfirst(40);
        mysinglelist.addfirst(50);
        system.out.println("头插:");
        mysinglelist.display();

        mysinglelist.addlast(100);
        mysinglelist.addlast(200);
        system.out.println("尾插:");
        mysinglelist.display();
        system.out.println();

        system.out.print("单链表的长度:");
        system.out.println(mysinglelist.getlength());
        system.out.println();

        mysinglelist.addindex(1,15);
        system.out.println("任意位置插入:");
        mysinglelist.display();
        system.out.println();

        system.out.println("查找是否包含关键字 key 在单链表中:");
        system.out.println("查找关键字125:"+mysinglelist.contains(125));
        system.out.println("查找关键字30:"+mysinglelist.contains(30));
        system.out.println();

        system.out.println("删除第一次出现的关键字为 key 的节点:");
        system.out.println("删除头节点50:");
        mysinglelist.remove(50); //删除头节点
        mysinglelist.display();
        system.out.println("删除中间节点30:");
        mysinglelist.remove(30); // 删除中间节点
        mysinglelist.display();
        system.out.println("删除尾节点200:");
        mysinglelist.remove(200); // 删除尾节点
        mysinglelist.display();
        system.out.println();

        system.out.println("删除第一次出现的关键字为 key 的节点:");
        mysinglelist.addfirst(20);
        mysinglelist.display();
        mysinglelist.removeallkey(20);
        mysinglelist.display();
        system.out.println();

        system.out.print("单链表的长度:");
        system.out.println(mysinglelist.getlength());
        system.out.println();

        // 测试内存泄漏
        try {
            thread.sleep(1000);
            system.out.println("睡醒了");
        } catch (interruptedexception e) {
            e.printstacktrace();
        }
    }
}

4. 测试结果

Java实现单链表的操作

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

相关标签: java 单链表