最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(3.5)从链表中删除元素

    从链表中删除元素

    其实有了前面的基础,其实完成删除操作也是很容易的。

    这里我们继续使用虚拟头结点,删除元素如果使用虚拟头结点会方便很多。

    假设我们想删除索引为2的元素,这个过程中,我们也需要找到待删除元素之前的节点,所以我们需要使用prev这样一个节点。

    首先找到待删除元素2之前的节点,也就是1,prev对应的next就是我们要删除的节点了。

    我们称之为delNode,接下来要做的就是将Prev节点的next指针赋值成为delNode.next。

    如上图所示,prev节点直接跳过了原本的next节点,指向了原本next节点的next节点,这样就相当于把2给跳过去了。

    从某种意义来讲,等同于把2这个节点删除了,当然为了方便java能回收这个空间,我们还要手动让2这个节点的next和链表脱离开,也就是让delNode的next指向Null。

    代码演示

    public class LinkedList {
    
        private class Node{
            public E e;
            public Node next;
    
            public Node(E e, Node next){
                this.e = e;
                this.next = next;
            }
    
            public Node(E e){
                this(e, null);
            }
    
            public Node(){
                this(null, null);
            }
    
            @Override
            public String toString(){
                return e.toString();
            }
        }
    
        private Node dummyHead;
        private int size;
    
        public LinkedList(){
            dummyHead = new Node();
            size = 0;
        }
    
        // 获取链表中的元素个数
        public int getSize(){
            return size;
        }
    
        // 返回链表是否为空
        public boolean isEmpty(){
            return size == 0;
        }
    
        // 在链表的index(0-based)位置添加新的元素e
        // 在链表中不是一个常用的操作,练习用:)
        public void add(int index, E e){
    
            if(index < 0 || index > size)
                throw new IllegalArgumentException("Add failed. Illegal index.");
    
            Node prev = dummyHead;
            for(int i = 0 ; i < index ; i ++)
                prev = prev.next;
    
            prev.next = new Node(e, prev.next);
            size ++;
        }
    
        // 在链表头添加新的元素e
        public void addFirst(E e){
            add(0, e);
        }
    
        // 在链表末尾添加新的元素e
        public void addLast(E e){
            add(size, e);
        }
    
        // 获得链表的第index(0-based)个位置的元素
        // 在链表中不是一个常用的操作,练习用:)
        public E get(int index){
    
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Get failed. Illegal index.");
    
            Node cur = dummyHead.next;
            for(int i = 0 ; i < index ; i ++)
                cur = cur.next;
            return cur.e;
        }
    
        // 获得链表的第一个元素
        public E getFirst(){
            return get(0);
        }
    
        // 获得链表的最后一个元素
        public E getLast(){
            return get(size - 1);
        }
    
        // 修改链表的第index(0-based)个位置的元素为e
        // 在链表中不是一个常用的操作,练习用:)
        public void set(int index, E e){
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Set failed. Illegal index.");
    
            Node cur = dummyHead.next;
            for(int i = 0 ; i < index ; i ++)
                cur = cur.next;
            cur.e = e;
        }
    
        // 查找链表中是否有元素e
        public boolean contains(E e){
            Node cur = dummyHead.next;
            while(cur != null){
                if(cur.e.equals(e))
                    return true;
                cur = cur.next;
            }
            return false;
        }
    
        // 从链表中删除index(0-based)位置的元素, 返回删除的元素
        // 在链表中不是一个常用的操作,练习用:)
        public E remove(int index){
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Remove failed. Index is illegal.");
    
            Node prev = dummyHead;
            for(int i = 0 ; i < index ; i ++)
                prev = prev.next;
    
            Node retNode = prev.next;
            prev.next = retNode.next;
            retNode.next = null;
            size --;
    
            return retNode.e;
        }
    
        // 从链表中删除第一个元素, 返回删除的元素
        public E removeFirst(){
            return remove(0);
        }
    
        // 从链表中删除最后一个元素, 返回删除的元素
        public E removeLast(){
            return remove(size - 1);
        }
    
        // 从链表中删除元素e
        public void removeElement(E e){
    
            Node prev = dummyHead;
            while(prev.next != null){
                if(prev.next.e.equals(e))
                    break;
                prev = prev.next;
            }
    
            if(prev.next != null){
                Node delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
                size --;
            }
        }
    
        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
    
            Node cur = dummyHead.next;
            while(cur != null){
                res.append(cur + "->");
                cur = cur.next;
            }
            res.append("NULL");
    
            return res.toString();
        }
    }
    

    接下来测试一下删除功能

    public class Main {
    
        public static void main(String[] args) {
    
            LinkedList linkedList = new LinkedList<>();
            for(int i = 0 ; i < 5 ; i ++){
                linkedList.addFirst(i);
                System.out.println(linkedList);
            }
    
            linkedList.add(2, 666);
            System.out.println(linkedList);
    
            linkedList.remove(2);
            System.out.println(linkedList);
    
            linkedList.removeFirst();
            System.out.println(linkedList);
    
            linkedList.removeLast();
            System.out.println(linkedList);
        }
    }
    
    

    运行程序,分析结果

    链表的时间复杂度分析

    添加操作

    删除操作

    修改操作

    查找操作

    时间复杂度总结

    源码下载

    [dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

    导航目录

    [dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(3.5)从链表中删除元素

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 169会员总数(位)
    • 3735资源总数(个)
    • 1本周发布(个)
    • 0 今日发布(个)
    • 443稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级