Java实现单链表的一些操作

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java实现单链表的一些操作，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3021字，纯文字阅读大概需要5分钟。

内容图文

首先来构造数据结构，这里单链表的节点类是以内部类的形式出现

数据结构

节点类：

节点类中应该有数据域和指针域

	/**
     * 节点类
     */
    class Entry {
        //数据域
        private int data;
        //指针域
        private Entry next;

        //无参构造函数
        public Entry() {
            this(0,null);
        }

        //有参构造函数
        public Entry(int data, Entry next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public Entry getNext() {
            return next;
        }

        public void setNext(Entry next) {
            this.next = next;
        }
    }

单链表类

      来写外部类，外部类就是单链表类，单链表类需要维护一个头结点，头结点的数据域是不存放数据的，头结点的指针域为空。

public class MiNiLinkedList {
    //头结点
    private Entry head;

    public MiNiLinkedList() {
        this.head = new Entry(0,null);
    }
}

注意，节点类是单链表类的一个内部类

操作

头插法

      插入节点是从头开始插入，思路很简单，直接把生成的新节点插入到头节点的后面，注意不能丢失原来头结点后面的节点，所以需要先把原来的节点链到新节点的后面，再把新节点接到头结点的后面。

时间复杂度：O（1）

    //从头插入节点
    public void insertHead(int data) {
        //new一个新节点
        Entry entry = new Entry(data, null);
        //防止后面的节点丢失，先把后面的节点接到新节点的后面
        entry.next = head.getNext();
        //把新节点接入到头结点的后面
        head.next = entry;
    }

尾插法

      从链表的末尾插入元素，首先需要定义一个指针插入到链表的末尾，然后把新生成的节点插入到末尾的后面。

由于需要遍历到链表的后面，所以时间复杂度是O（n）

    //从尾进行插入
    public void insertTail(int data) {
        //new一个新的节点
        Entry entry = new Entry(data, null);
        //定义一个指针,遍历到链表的最后
        Entry last = head;

        while(last.next != null) {
            last = last.next;
        }
        last.next = entry;
    }

      有时经常进行尾插操作时，为了不用每次插入都遍历到链表的最后，可以维护一个尾节点，如果维护尾结点需要注意几点：

1. 在第一次头插的时候，需要移动尾结点到新节点
2. 每一次尾插的时候都需要更新尾结点
3. 在删除的时候，如果删除的节点是尾结点，那么需要把尾结点往前移动

删除第一个值为data的节点

      定义一个指针指向前一个节点，遍历链表，当下一个节点是要找的节点的时候，通过当前节点删除该节点。

    //删除第一个值为data的节点
    public boolean removeFirst(int data) {
        //定义一个指针，找到待删除节点的前一个节点
        Entry entry = head;
        while(entry.next!=null && entry.next.data!=data){
            entry = entry.next;
        }

        //删除待删节点
        if(entry.next == null) {
            //遍历到最后
            return false;
        } else {
            //删除该节点
            entry.next = entry.next.next;
            return true;
        }
    }

      可以看到我的代码实现是维护了一个指针，其实也可以维护两个指针，移动的时候两个指针同时移动，这样理解起来比较容易。

删除所有值为data的节点

      刚才删除第一个值为data的节点是遍历到对应的位置，指针就停下来，而删除所有值为data的节点，在遍历的过程中是不停止的，如果找到了值为data的节点，就删除该节点，然后继续往下遍历。

    //删除所有值为data的节点
    public void removeAll(int data) {
        //定义一个指针，找到待删除节点的前一个节点
        Entry entry = head;
        while(entry.next!=null){
            if(entry.next.data == data) {
                entry.next = entry.next.next;
            } else {
                entry = entry.next;
            }
        }
    }

查询

查询的逻辑比较简单，遍历整个链表即可

    public boolean query(int data) {
        //定义一个指针
        Entry cur = head.next;

        //逐一遍历
        while(cur != null) {
            if(cur.data == data) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

内容总结

以上是互联网集市为您收集整理的Java实现单链表的一些操作全部内容，希望文章能够帮你解决Java实现单链表的一些操作所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端