精华内容
下载资源
问答
  • 和往期一样,先贴出写的...通过递归从尾到头输出单链表* 反转链表链表特点链表由一个一个节点通过地址的指向连接内存中的地址不联系,但是逻辑地址是连续的头节点很重要,由头节点开始遍历,完成查找,添加,删除...
    和往期一样,先贴出写的比较好的博客Java3y(知乎也有他的账号)博客:Java实现单向链表
    博客内容:
    * 链表的遍历,查找,插入节点,删除节点等
    * 排序
    * 找到链表中倒数第k个节点
    * 删除链表重复数据
    *查询链表的中间节点* 通过递归从尾到头输出单链表* 反转链表

    链表特点

    • 链表由一个一个节点通过地址的指向连接
    • 在内存中的地址不联系,但是逻辑地址是连续的

    d0005b55b6f2756cc64f18d3a6c7a01e.png
    • 头节点很重要,由头节点开始遍历,完成查找,添加,删除等操作

    代码

    1. 代码思路
    • 头节点很重要,其地址不能丢失
    • 在Java中,节点相当于类,类中的数据必定有,数据和下一个节点的地址
    • temp节点很重要,遍历的适合就要用到它,temp = head

    2. 代码

    /**
     * 1.带头节点的链表
     * 2.链表关键元素:头节点,节点类,下一个节点
     * 3.需求:增,删,查,遍历
     * 4.拓展需求:求特定位置的元素,链表反转
     */
    
    public class LinkedList<T> {
        //头节点
        private Node head;
        //节点
        private class Node{
            //数据域
            T data;
            //指针域(下一个节点)
            Node next;
            public Node(T data){
                this.data = data;
            }
        }
        //构造函数
        public LinkedList(){
            head = new Node(null);
            head.next = null;
        }
    
        /**
         * 获取长度
         */
        public int size(){
            Node temp = head;
            int size = 0;
            while (temp.next != null){
                temp = temp.next;
                size ++;
            }
            return size;
        }
    
        /**
         *在特定位置插入节点
         * 记住:一定要先判断参数是否合法
         */
        public void addNode(T data,int index){
            if(index < 0 || index > size()){
                throw new RuntimeException("参数不合法");
            }
            Node newNode = new Node(data);
            Node temp = head;
            for (int i = 0; i < size(); i++) {
                temp = temp.next;
            }
            //插入操作,此处要注意顺序
            newNode.next = temp.next;
            temp.next = newNode;
        }
    
        /**
         * 删除节点
         */
        public void deleteNode(int index){
            //注意此处应为size()-1,因为我的下标是从0开始的
            if(index < 0 || index > size()-1){
                throw new RuntimeException("参数不合法");
            }
            Node temp = head;
            for (int i = 0; i < size(); i++) {
                temp = temp.next;
            }
            //删除操作
            temp.next = temp.next.next;
        }
    
        /**
         * 取节点元素
         */
        public T getData(int index){
            //注意此处应为size()-1,因为我的下标是从0开始的
            if(index < 0 || index > size()-1){
                throw new RuntimeException("参数不合法");
            }
            Node temp = head;
            for (int i = 0; i < size(); i++) {
                temp = temp.next;
            }
            //取数据
            return temp.data;
        }
    }
    

    总结

    这里只完成了最简单操作,更多深入的操作看头部大佬的博客,有人写的比我好,我就不赘述了,

    这里我给出学习链表的经验:

    1. 一定要动手敲代码,要动脑思考为什么要怎么操作
    2. 动笔画,很多时候转不过来,你就 画一下链表是如何添加,删除的,然后把画图的思路运用到代码中。
    展开全文
  • 链表

    2019-03-09 23:31:52
    链表的实现:链表储存有序的元素集合,但是和数组不同的是,链表中的元素在内存中不是连续放置的,每个元素由一个储存元素本身的节点和一个指向下一个元素的引用(指针、...在链表的开头添加一个元素: 在链...

    链表的实现:链表储存有序的元素集合,但是和数组不同的是,链表中的元素在内存中不是连续放置的,每个元素由一个储存元素本身的节点和一个指向下一个元素的引用(指针、链接)

    向空的链表中添加一个元素:

     

    向不为空的链表尾部添加元素:

     

    从链表中移除第一个元素:

     

     从链表中移除最后一个元素:

     

     从链表中间移除一个元素:

     

    在链表的开头添加一个元素:

     

     

    在链表的最后添加一个元素:

     

     

    在链表的中间添加一个元素:

     

     

    function LinkedList() {
            let Node = function (element) {
                this.element = element;
                this.next = null;
            };
            let length = 0;
            let head = null;
            this.append = function(element){
                //向列表尾部添加一个新的元素
               let node = new Node(element);
               let current;
               if(head === null){
                   head = node;
               }else{
                   current = head;
                   while(current.next){
                       current = current.next;
                   }
                   //找到最后一项,将其next 赋为node,建立连接
                   current.next = node;
               }
               length++;//更新列表的长度
            };
    
            this.insert = function (position, element) {
                //向列表特定的位置插入一个新的项
    
                //检查是否越界
                if(position >= 0 && position < length){
                    let node = new Node(element),
                        current = head,
                        previous,
                        index = 0;
                    if(position === 0){ //在第一个位置插入
                        node.next = current;
                        head = node;
                    }else{
                        while(index++ < position){
                            previous = current;
                            current = current.next;
                        }
                        node.next = current;
                        previous.next = node;
                    }
                    length--;
                    return true;
                }else{
                    return false;
                }
            };
            this.removeAt = function(position){
                //从列表特定的位置删除一项
    
                //检查是否越界
                if(position > -1 && position < length){
                    let current = head,
                        previous,
                        index = 0;
                    //移除第一项
                    if(position === 0){
                        head = current.next;
                    }else{
                        while(index++ < position){
                            previous = current;
                            current = current.next;
                        }
                        previous.next = current.next;
                    }
                    length--;
                    return current.element;
                }else{
                    return null;
                }
            };
    
            this.indexOf = function (element) {
                //返回元素在列表中的索引,如果列表中没有该元素就返回-1
                let current = head,
                    index = -1;
                while(current){
                    if(element === current.element){
                        return index;
                    }
                    index++;
                    current = current.next;
                }
                return -1;
            };
            this.isEmpty = function () {
                //列表中不包含任何元素就返回true,否则返回false
                return length === 0;
            };
            this.size = function () {
                //返回链表的元素个数
                return length;
            };
            this.toString = function () {
                //重写js对象默认的 toString 方法
                let current = head,
                    string = '';
                while(current){
                    string += current.element;
                }
                return string;
            };
            this.remove = function (element) {
                //从列表中移除一项
                let index = this.indexOf(element);
                return this.removeAt(index);
            };
           this.getHead = function () {
                return head;
           };
        }

     

    双向链表:连接是双向的——一个链向下一个元素,一个链向前一个元素

     

    在开头插入一个元素:

     

    在链表最后添加一个元素:

     

     

    在链表中间插入一个元素:

     

     

    双向链表移除第一个元素:

     

     

    最后一个位置移除元素:

     

    从双向链表中间位置移除一个元素:

    具体实现:

    }function DoublyLinkedList() {
    
        var Node = function(element){
    
            this.element = element;
            this.next = null;
            this.prev = null;
        };
    
        var length = 0;
        var head = null;
        var tail = null;
    
        this.append = function(element){
    
            var node = new Node(element),
                current;
    
            if (head === null){ //链表的第一项
                head = node;
                tail = node;
            } else {
    
            /
                tail.next = node;
                node.prev = tail;
                tail = node;
            }
    
            length++; //更新链表长度
        };
    
        this.insert = function(position, element){
    
            //检查边界值
            if (position >= 0 && position <= length){
    
                var node = new Node(element),
                    current = head,
                    previous,
                    index = 0;
    
                if (position === 0){ //添加在链表的第一个位置
    
                    if (!head){
                        head = node;
                        tail = node;
                    } else {
                        node.next = current;
                        current.prev = node;
                        head = node;
                    }
    
                } else  if (position === length) { //最后的位置
    
                    current = tail;
                    current.next = node;
                    node.prev = current;
                    tail = node;
    
                } else {
                    while (index++ < position){
                        previous = current;
                        current = current.next;
                    }
                    node.next = current;
                    previous.next = node;
    
                    current.prev = node;
                    node.prev = previous;
                }
    
                length++; //更新链表长度
    
                return true;
    
            } else {
                return false;
            }
        };
    
        this.removeAt = function(position){
    
            //检查是否超出边界
            if (position > -1 && position < length){
    
                var current = head,
                    previous,
                    index = 0;
    
                //移除第一个元素
                if (position === 0){
    
                    head = current.next;
    
                    //只有一个元素的情况
                    if (length === 1){
                        tail = null;
                    } else {
                        head.prev = null;
                    }
    
                } else if (position === length-1){ //最后一项
    
                    current = tail;
                    tail = current.prev;
                    tail.next = null;
    
                } else {
    
                    while (index++ < position){
    
                        previous = current;
                        current = current.next;
                    }
    
                    // 将previous和  current's next 连接起来——跳过current
                    previous.next = current.next;
                    current.next.prev = previous;
                }
    
                length--;
    
                return current.element;
    
            } else {
                return null;
            }
        };
    
        this.remove = function(element){
    
            var index = this.indexOf(element);
            return this.removeAt(index);
        };
    
        this.indexOf = function(element){
    
            var current = head,
                index = -1;
    
            //检查第一个位置
            if (element == current.element){
                return 0;
            }
    
            index++;
    
            //检查中间位置元素
            while(current.next){
    
                if (element == current.element){
                    return index;
                }
    
                current = current.next;
                index++;
            }
    
            //检查链表尾部元素
            if (element == current.element){
                return index;
            }
    
            return -1;
        };
    
        this.isEmpty = function() {
            return length === 0;
        };
    
        this. size = function() {
            return length;
        };
    
        this.toString = function(){
    
            var current = head,
                s = current ? current.element : '';
    
            while(current && current.next){
                current = current.next;
                s += ', ' + current.element;
            }
    
            return s;
        };
    
        this.inverseToString = function() {
    
            var current = tail,
                s = current ? current.element : '';
    
            while(current && current.prev){
                current = current.prev;
                s += ', ' + current.element;
            }
    
            return s;
        };
    
        this.print = function(){
            console.log(this.toString());
        };
    
        this.printInverse = function(){
            console.log(this.inverseToString());
        };
    
        this.getHead = function(){
            return head;
        };
    
        this.getTail = function(){
            return tail;
        }
    

     

    循环链表:

    单向循环链表:

    最后一个元素的指针指向第一个元素,而不是引用null

    双向链表:指向head 元素的 tail.prev ,指向tail 元素的 head.prev

     

    function CircularLinkedList() {
    
        var Node = function(element){
    
            this.element = element;
            this.next = null;
        };
    
        var length = 0;
        var head = null;
    
        this.append = function(element){
    
            var node = new Node(element),
                current;
    
            if (head === null){ //链表为空,添加第一个元素
                head = node;
            } else {
    
                current = head;
    
                //迭代链表直到找到最后一个元素
                while(current.next !== head){ //最后一个元素设置为head
                    current = current.next;
                }
    
                //最后一个元素链接到node
                current.next = node;
            }
    
            //设置node.next 链接到head 构成一个循环链表
            node.next = head;
    
            length++; //更新链表长度
        };
    
        this.insert = function(position, element){
    
            //检查是否超出边界
            if (position >= 0 && position <= length){
    
                var node = new Node(element),
                    current = head,
                    previous,
                    index = 0;
    
                if (position === 0){ //在循环链表开头添加
    
                    node.next = current;
    
                    //设置最后一个元素
                    while(current.next !== head){ //最后一个元素设置为head
                        current = current.next;
                    }
    
                    head = node;
                    current.next = head;
    
                } else {
                    while (index++ < position){
                        previous = current;
                        current = current.next;
                    }
                    node.next = current;
                    previous.next = node;
    
                    if (node.next === null){ 
                        node.next = head;
                    }
                }
    
                length++; //更新链表长度
    
                return true;
    
            } else {
                return false;
            }
        };
    
        this.removeAt = function(position){
    
            //检查是否超出边界
            if (position > -1 && position < length){
    
                var current = head,
                    previous,
                    index = 0;
    
                //移除开头元素
                if (position === 0){
    
                    while(current.next !== head){ //先设置最后一个元素的指向
                        current = current.next;
                    }
    
                    head = head.next;
                    current.next = head;
    
                } else { //末尾元素不需要更新
    
                    while (index++ < position){
    
                        previous = current;
                        current = current.next;
                    }
    
                    //将previous.next 和 current.next链接起来
                    previous.next = current.next;
                }
    
                length--;
    
                return current.element;
    
            } else {
                return null;
            }
        };
    
        this.remove = function(element){
    
            var index = this.indexOf(element);
            return this.removeAt(index);
        };
    
        this.indexOf = function(element){
    
            var current = head,
                index = -1;
    
            //检查开头元素
            if (element == current.element){
                return 0;
            }
    
            index++;
    
            //检查链表中间元素
            while(current.next !== head){
    
                if (element == current.element){
                    return index;
                }
    
                current = current.next;
                index++;
            }
    
            //检查链表最后元素
            if (element == current.element){
                return index;
            }
    
            return -1;
        };
    
        this.isEmpty = function() {
            return length === 0;
        };
    
        this.size = function() {
            return length;
        };
    
        this.getHead = function(){
            return head;
        };
    
        this.toString = function(){
    
            var current = head,
                s = current.element;
    
            while(current.next !== head){
                current = current.next;
                s += ', ' + current.element;
            }
    
            return s.toString();
        };
    
        this.print = function(){
            console.log(this.toString());
        };
    }

     

    (这个链表真的是晦涩难懂,绕来绕去的,但是跟结合图片来理解还是可以接受的,这恐怕是有史以来我最长的记录笔记的博文)

    展开全文
  • 查找未知链表长度的中间结点 众所周知,链表是不知道长度的,如果想知道长度只能通过遍历一遍链表才可得知,因此对于查找未知链表长度的...注:initLink为初始化链表,即添加节点添加结点的方法为尾插法,其他文

    查找未知链表长度的中间结点

    众所周知,链表是不知道长度的,如果想知道长度只能通过遍历一遍链表才可得知,因此对于查找未知链表长度的中间结点可以有很多方法。
    最简单的方法就是通过遍历一边链表得到长度L,再通过遍历L/2的链表得到中间结点,此时时间复杂度就是o(L+L/2).
    而另一种更简便方法则为通过建立两个指针,第一个指针为第二个指针速度的两倍,那么当第一个指针到达链表末尾的时候,就可以得知此时第二个指针在中间结点。
    代码如下:
    注:initLink为初始化链表,即添加根节点,添加结点的方法为尾插法,在其他文章中有写到,在这里直接使用。

    public class ForMidNode {
        public void forMidNode(Linkedlist linkedlist){
            //first 的速度是follow的两倍,当first到末尾时,follow位于中间结点
            Node first =new Node();
            Node follow=new Node();
    //先将两个指针放于同一结点,默认链表不为空,为空加个判断即可
            first=linkedlist.root.next;
            follow=linkedlist.root.next;
            int i=1;
            while (first.next!=null){
                first=first.next;
                if(i%2==0){
                    follow=follow.next;
                }
                i++;
                System.out.println("此时的first指向的数组是"+first.getData());
                System.out.println("此时的follow指向的数组是"+follow.getData());
            }
            System.out.println("最后的first指向的数组是"+first.getData());
            System.out.println("中间结点的数值是:"+follow.getData());
        }
        public static void main(String [] args){
            ForMidNode forMidNode=new ForMidNode();
            Linkedlist linkedlist=new Linkedlist();
            linkedlist.initLink();
            linkedlist.insertForTail(1);
            linkedlist.insertForTail(2);
            linkedlist.insertForTail(3);
            linkedlist.insertForTail(4);
            linkedlist.insertForTail(5);
            linkedlist.insertForTail(6);
            linkedlist.insertForTail(7);
            linkedlist.insertForTail(8);
            linkedlist.insertForTail(9);
           forMidNode.forMidNode(linkedlist);
        }
    }
    

    运行结果:
    在这里插入图片描述

    而下边的方法是刚刚方法的改进,在上边方法中可以看到,虽然说我们是在同时时间进行两个指针的遍历,但是我们采用的方法是,第一个指针一直移动,第二个指针等一段时间停止移动,这样的等待就会造成时间浪费,而且第一个指针也会对每一个结点进行遍历,因此我们对此进行改进,让第一个的指针的速度真正成为第二个指针速度的两倍,即让第一个指针永远指向next的next(如果next的next不为空的情况下),代码如下:

    public void forMidNode1(Linkedlist linkedlist){
            //first 的速度是follow的两倍,当first到末尾时,follow位于中间结点
            Node first =new Node();
            Node follow=new Node();
    
            first=linkedlist.root.next;
            follow=linkedlist.root.next;
    
            while (first.next!=null){
    
                if(first.next.next!=null){
                    first=first.next.next;
                    follow=follow.next;
                }
                 else first=first.next;
                System.out.println("此时的first指向的数组是"+first.getData());
                System.out.println("此时的follow指向的数组是"+follow.getData());
            }
            System.out.println("最后的first指向的数组是"+first.getData());
            System.out.println("中间结点的数值是:"+follow.getData());
        }
    

    运行结果:
    从运行结果来看,也可以发现少运行了很多环节。
    在这里插入图片描述

    展开全文
  • 4.数据结构--链表

    2018-08-18 00:33:00
    1.什么是链表 优点:不需要处理固定容量的问题 缺点:丧失了随机访问的能力 ...(2)在链表中间添加元素 (3)链表中添加节点的代码实现 public class LinkedList<E> { private class Node{ ...

    1.什么是链表

    优点:不需要处理固定容量的问题

    缺点:丧失了随机访问的能力

    2.数组和链表的对比

    3.在链表中添加元素

    (1)在链表头添加元素

    (2)在链表中间添加元素

    (3)链表中添加节点的代码实现

    public class LinkedList<E> {
        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 head;
        int size;
    
        public LinkedList(){
            head = null;
            size =0;
        }
    
        //获取链表中的元素个数
        public int getSize(){
            return size;
        }
    
        //返回链表是否为空
        public boolean isEmpty(){
            return size == 0;
        }
    
        //在链表头添加新的元素e
        public void addFirst(E e){
    //        Node node = new Node(e);
    //        node.next = head;
    //        head = node;
    
            head = new Node(e,head);
            size ++;
        }
    
        //在链表的index位置添加新元素e
        public void add(int index,E e){
            if(index < 0 || index > size)
                throw new IllegalArgumentException("Add failed.Illegal index.");
    
            if(index == 0)
                addFirst(e);
            else{
                Node prev = head;
                for(int i = 0;i < index -1;i ++)
                    prev =prev.next;
    //            Node node =new Node(e);
    //            node.next = prev.next;
    //            prev.next = node;
    
                prev.next =new Node(e,prev.next);
                size ++;
            }
        }
    
        //在链表末尾添加新的元素e
        public void addLast(E e){
            add(size,e);
        }
    }

    4.使用链表的虚拟头结点

    public class LinkedList<E> {
        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(null,null);
            size =0;
        }
    
        //获取链表中的元素个数
        public int getSize(){
            return size;
        }
    
        //返回链表是否为空
        public boolean isEmpty(){
            return size == 0;
        }
    
        //在链表的index位置添加新元素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);
        }
    }

    5.链表的遍历,查询和修改

    public class LinkedList<E> {
        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(null,null);
            size =0;
        }
    
        //获取链表中的元素个数
        public int getSize(){
            return size;
        }
    
        //返回链表是否为空
        public boolean isEmpty(){
            return size == 0;
        }
    
        //在链表的index位置添加新元素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位置的元素
        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位置的元素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;
        }
    
        @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<Integer> 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);
    //        0->NULL
    //        1->0->NULL
    //        2->1->0->NULL
    //        3->2->1->0->NULL
    //        4->3->2->1->0->NULL
    //        4->3->666->2->1->0->NULL
        }
    }

    6.链表元素的删除

    public class LinkedList<E> {
        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(null,null);
            size =0;
        }
    
        //获取链表中的元素个数
        public int getSize(){
            return size;
        }
    
        //返回链表是否为空
        public boolean isEmpty(){
            return size == 0;
        }
    
        //在链表的index位置添加新元素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位置的元素
        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位置的元素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位置的元素,返回删除的元素
        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);
        }
    
        @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<Integer> 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);
    //        0->NULL
    //        1->0->NULL
    //        2->1->0->NULL
    //        3->2->1->0->NULL
    //        4->3->2->1->0->NULL
    //        4->3->666->2->1->0->NULL
    
            linkedList.remove(2);
            System.out.println(linkedList);
    
            linkedList.removeFirst();
            System.out.println(linkedList);
    
            linkedList.removeLast();
            System.out.println(linkedList);
    //        0->NULL
    //        1->0->NULL
    //        2->1->0->NULL
    //        3->2->1->0->NULL
    //        4->3->2->1->0->NULL
    //        4->3->666->2->1->0->NULL
    //        4->3->2->1->0->NULL
    //        3->2->1->0->NULL
    //        3->2->1->NULL
        }
    }

    7.链表的时间复杂度分析

     

     8.使用链表实现栈

    public class LinkedListStack<E> implements Stack<E>{
        private LinkedList<E> list;
        public LinkedListStack(){
            list = new LinkedList<>();
        }
    
        @Override
        public int getSize(){
            return list.getSize();
        }
    
        @Override
        public boolean isEmpty(){
            return list.isEmpty();
        }
    
        @Override
        public void push(E e){
            list.addFirst(e);
        }
    
        @Override
        public E pop(){
            return list.removeFirst();
        }
    
        @Override
        public E peek(){
            return list.getFirst();
        }
    
        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
            res.append("Stack: top ");
            res.append(list);
            return res.toString();
        }
    
        public static void main(String[] args) {
            LinkedListStack<Integer> stack = new LinkedListStack<>();
            for(int i = 0;i < 5;i ++){
                stack.push(i);
                System.out.println(stack);
            }
            stack.pop();
            System.out.println(stack);
    //        Stack: top 0->NULL
    //        Stack: top 1->0->NULL
    //        Stack: top 2->1->0->NULL
    //        Stack: top 3->2->1->0->NULL
    //        Stack: top 4->3->2->1->0->NULL
    //        Stack: top 3->2->1->0->NULL
        }
    }

     9.数组栈和链表栈比较

    import java.util.Random;
    
    public class Main {//测试使用q运行opCount个enqueue和dequeue操作所需要的时间,单位:秒
        private static double testStack(Stack<Integer> stack,int opCount){
            long startTime = System.nanoTime();
            Random random = new Random();
            for(int i = 0; i < opCount; i++)
                stack.push(random.nextInt(Integer.MAX_VALUE));
            for(int i = 0;i < opCount; i++)
                stack.pop();
            long endTime = System.nanoTime();
            return (endTime - startTime) / 1000000000.0;
        }
    
        public static void main(String[] args) {
            int opCount = 10000000;
            //数组栈
            ArrayStack<Integer> arrayStack = new ArrayStack<>();
            double time1 = testStack(arrayStack,opCount);
            System.out.println("ArrayStack, time:" + time1 + "s");       // ArrayStack, time:4.220762637s
    
            //链表栈
            LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
            double time2 = testStack(linkedListStack,opCount);
            System.out.println("LinkedListStack, time:" + time2 + "s");  // LinkedListStack, time:6.295457665s
        }
    }

     10.改进我们的链表来实现队列

    public class LinkedListQueue<E> implements Queue<E> {
        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 head , tail;
        private int size;
    
        public LinkedListQueue(){
            head = null;
            tail = null;
            size = 0;
        }
    
        @Override
        public int getSize(){
            return size;
        }
    
        @Override
        public boolean isEmpty(){
            return size == 0;
        }
    
        @Override
        public void enqueue(E e){
            if(tail == null){
                tail = new Node(e);
                head = tail;
            }else{
                tail.next = new Node(e);
                tail = tail.next;
            }
            size ++;
        }
    
        @Override
        public E dequeue(){
            if(isEmpty())
                throw new IllegalArgumentException("cannot dequeue from an empty queue");
            Node retNode = head;
            head = head.next;
            retNode.next = null;
            if(head == null)
                tail = null;
            size --;
    
            return retNode.e;
        }
    
        @Override
        public E getFront(){
            if(isEmpty())
                throw new IllegalArgumentException("Queue is empty.");
            return head.e;
        }
    
        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
            res.append("Queue: front ");
    
            Node cur = head;
            while(cur != null){
                res.append(cur + "->");
                cur = cur.next;
            }
            res.append("NULL tail");
            return res.toString();
        }
    
        public static void main(String[] args) {
            LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
            for(int i = 0;i < 10;i ++){
                linkedListQueue.enqueue(i);
                System.out.println(linkedListQueue);
    
                if(i % 3 == 2){
                    linkedListQueue.dequeue();
                    System.out.println(linkedListQueue);
                }
            }
    //        Queue: front 0->NULL tail
    //        Queue: front 0->1->NULL tail
    //        Queue: front 0->1->2->NULL tail
    //        Queue: front 1->2->NULL tail
    //        Queue: front 1->2->3->NULL tail
    //        Queue: front 1->2->3->4->NULL tail
    //        Queue: front 1->2->3->4->5->NULL tail
    //        Queue: front 2->3->4->5->NULL tail
    //        Queue: front 2->3->4->5->6->NULL tail
    //        Queue: front 2->3->4->5->6->7->NULL tail
    //        Queue: front 2->3->4->5->6->7->8->NULL tail
    //        Queue: front 3->4->5->6->7->8->NULL tail
    //        Queue: front 3->4->5->6->7->8->9->NULL tail
        }
    }

     11.链表队列和数组队列、循环队列进行比较

    import java.util.Random;
    
    public class Main {//测试使用q运行opCount个enqueue和dequeue操作所需要的时间,单位:秒
        private static double testQueue(Queue<Integer> q,int opCount){
            long startTime = System.nanoTime();
            Random random = new Random();
            for(int i = 0; i < opCount; i++)
                q.enqueue(random.nextInt(Integer.MAX_VALUE));
            for(int i = 0;i < opCount; i++)
                q.dequeue();
            long endTime = System.nanoTime();
            return (endTime - startTime) / 1000000000.0;
        }
    
        public static void main(String[] args) {
            int opCount = 100000;
            //数组队列
            ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
            double time1 = testQueue(arrayQueue,opCount);
            System.out.println("ArrayQueue, time:" + time1 + "s");       //ArrayQueue, time:4.859302024s
    
            //循环队列
            LoopQueue<Integer> loopQueue = new LoopQueue<>();
            double time2 = testQueue(loopQueue,opCount);
            System.out.println("LoopQueue, time:" + time2 + "s");        //LoopQueue, time:0.019878675s
    
            //链表队列
            LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
            double time3 = testQueue(linkedListQueue,opCount);
            System.out.println("LinkedListQueue, time:" + time3 + "s");  //LinkedListQueue, time:0.015294216s
        }
    }

     12.删除链表中的结点(https://leetcode-cn.com/problems/remove-linked-list-elements/description/)

    删除链表中等于给定值 val 的所有节点。

    示例:

    输入: 1->2->6->3->4->5->6, val = 6
    输出: 1->2->3->4->5
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode removeElements(ListNode head, int val) {
            //删除头结点
            while(head != null && head.val == val){
                ListNode delNode = head;
                head = head.next;
                delNode.next = null;
            }
    
            if(head == null)
                return null;
    
            ListNode prev = head;
            while(prev.next != null){
                if(prev.next.val == val){
                    ListNode delNode = prev.next;
                    prev.next = delNode.next;
                    delNode.next = null;
                }else{
                    prev = prev.next;
                }
            }
    
            return head;
        }
    }

    进一步优化,增加虚拟头结点

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode removeElements(ListNode head, int val) {
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
    
            ListNode prev = dummyHead;
            while(prev.next != null){
                if(prev.next.val == val){
                    ListNode delNode = prev.next;
                    prev.next = delNode.next;
                    delNode.next = null;
                }else{
                    prev = prev.next;
                }
            }
    
            return dummyHead.next;
        }
    }

     调用实例:

    public class Main {
        public static void main(String[] args) {
           int[] nums = {1, 2, 6, 3, 4, 5, 6};
           ListNode head = new ListNode(nums);
           System.out.println(head);  //1->2->6->3->4->5->6->NULL
    
           ListNode res = (new Solution()).removeElements(head , 6);
           System.out.println(res);   //1->2->3->4->5->NULL
        }
    }

     

     

    转载于:https://www.cnblogs.com/zouke1220/p/9496003.html

    展开全文
  • 1.链表合并 int main(){ node *phead1 = NULL;//头结点不分配内存 phead1 = ... //addback是尾部添加节点,也就是将2插入怕head1链表的尾部。 phead1 = addback(phead1, 4); phead1 = addback(phead1, 6); phead1...
  • 双向链表

    2020-12-05 09:45:05
    2.在链表尾部和中间操作有区别,需要处理下一个节点是否为空 3.双向链表需要两个指针prev和next,prev指向前一个节点,next指向下一个节点 示意图 class DoubleLinkedList { //双向链表初始化一个头节点 ...
  • 和往期一样,先贴出写的...通过递归从尾到头输出单链表* 反转链表链表特点链表由一个一个节点通过地址的指向连接内存中的地址不联系,但是逻辑地址是连续的头节点很重要,由头节点开始遍历,完成查找,添加,删除...
  • 双向链表的设计(1)

    2019-12-10 11:12:20
    双向链表的设计双向链表节点的定义双向链表的增和删在头结点添加链表元素在尾节点添加元素在链表中间添加元素删除链表中的元素获取索引值index对应的链结点的值获取链表的长度将链表中的元素输出完整代码插入链接与...
  • 常见的链表操作

    2019-03-14 14:56:15
    首先是单链表的基本操作:链表的插入,这里使用的是头插法,并且添加了哨兵节点,也就是头结点,这样可以不用考虑头结点的边界问题,具体C++代码如下: 1、链表的插入 struct SingleLi...
  • 双向链表比单项链表多了一个指向...还有一个区别是在有序添加数据时向尾节点添加数据和在链表中间添加数据在单向链表中时相同的操作,在双向链表中必须加以区分。 代码如下: ```java package linkedlist; public ...
  • 实现一个调整链表的函数,将链表调整为左边部分都是值小于pivot的节点中间部分都是值等于pivot的节点,右部分都是值大于pivot的节点 分析 根据题目可得,与之前的快排原型荷兰国旗问题十分相似。但是原问题的数据...
  • 文章目录 第三章 Caché 链表原理链表单向链表双向链表完整实例节点类链表类调用添加节点删除头节点删除中间节点删除尾节点 第三章 Caché 链表原理 链表 是一种物理上非连续,非顺序的数据结构,由若干节点组成...
  • C#双向链表简例

    2015-12-31 10:34:10
    双向链表顾名思义最大的特点就是...此,双向链表实现了链表基本的一些操作,链表头/尾添加节点、中间添加节点、删除节点、遍历链表(前->后/后->前遍历),废话不多说,看代码... using System; namespace OverrideT
  • 链表的基本操作

    2019-03-24 16:12:53
    2.添加节点(添加至头部、添加至尾部); 3.插入节点到中间位置(一次循环); 4.删除指定位置的元素; 5.查询某个值是否在链表中,如果在输出最后出现的位置。 #include<stdio.h> #include<stdlib.h> #...
  • 链表 单链表:链表中的每个元素实际上是一个单独的对象,而所有对象都通过每...利用快慢指针(有时候需要用到三个指针)(例如:链表翻转,寻找倒数第k个元素,寻找链表中间位置的元素,判断链表是否有环) 构建一个虚
  • 数据结构之链表

    2018-01-02 23:28:47
    什么是链表链表是一种线性表,是一种物理存储单元上非连续非顺序的存储结构。链表由一系列的节点构成,节点在运行时动态生成,每...4、元素可以从中间添加或者移除。 链表的缺点: 1、因为指针的存在,相对...
  • 数组中可以直接访问任何位置的任何元素,而链表中想访问链表中间的任一元素,需要从表头开始迭代链表直到找到所需的元素 2. 单链表 2.1 创建链表 // 作为默认的相等性比较函数 function defaultEquals(a, b) { ...
  • 数据结构-链表

    2019-06-23 17:35:06
    链表 需要存储大量的元素时数组可能是最常用的数据结构,但是也存在一定的局限性:数组的大小是固定的,数组的起点或者中间插入...链表在添加或者移除元素时不需要移动元素,需要使用指针。但是访问任何位置的...
  • 用JS实现链表

    2018-12-10 19:43:00
    链表特点:链表存储有序的元素集合,但不同于数组,链表中的元素内存中并不是连续放置的。...数组的另一个细节是可以直接访问任何位置的元素,而想要访问链表中间的一个元素,需要从起点开始迭代链...
  • 链表数据结构 链表是存储有序元素的集合,但不同于数组,链表...链表的缺点:要想访问链表中间的一个元素,需要从起点开始迭代链表直到找到所需要的元素,因此查询链表中的元素会比数组慢 链表结构现实生活中的列...
  • 单向链表的节点由两部分组成,一个是值,一个是下一个节点的引用(指针)。...在链表中间或尾部添加,效率很低。 以下是根据链表的原理进行的简单的实现,不一定严谨和健壮 java实现的代码如下...
  • JavaScript中的单向链表

    2018-10-03 20:47:53
    链表存储有序的元素集合,但不同于数组,链表中的元素内存中并不是连续放置的。每个元素由一个存储元素本身的...数组的另一个细节是可以直接访问任何位置元素,而要想访问链表中间的一个元素,需要从起点(表头)...
  • js数据结构之链表

    2017-06-19 20:48:32
    链表存储有序的元素集合,但不同于数组,链表中的元素内存中并不是连续放置的。...数组的另一个细节是可以直接访问任何位置的任何元素,而要想访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找
  • 简单谈下链表

    2020-05-18 09:32:00
    链表存储有序的元素集合,但不同于数组,链表的元素内存中不是连续放置的,每个元素由一个存储元素本身的节点个指向下一个元素的引用组成。  相对于传统的数组,链表的一个好处在于,添加或移除元素的时候不...
  • 单链表 概述 内存中不是连续的,以节点储存的,每个...添加节点分为添加到末尾,和添加到中间 添加到末尾:需要一个临时节点作为指针,开始时指向头节点,遍历时根据节点的next找到下一个节点,每次让temp=temp.next
  • 使用双指针遍历遍历两个链表,比较后将节点添加到新链表的末尾。 反思:知道要使用双指针,但是并未想到设置哨兵和尾指针(指向新链表)。一开始的思路是将第二个链表的节一 个一个插入到第一个链表中。所以插入有三...
  • 数组和链表的区别

    千次阅读 2012-07-13 11:57:21
    1、 数组是一块连续的空间,声明时长度要确定 链表是一块不连续的动态空间,长度可变 2、 数组的优点是速度快,数据...链表的特性是在中间任意位置添加删除元素的都非常的快,不需要移动其它的元素。 链表顾名思
  • JS实现链表数据结构

    2019-08-15 21:16:13
    链表存储有序的元素集合,但不同于数组,链表中的元素内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(指针或链接)组成。 链表的一个好处在于,添加或者移除元素的时候不...

空空如也

空空如也

1 2 3 4
收藏数 72
精华内容 28
关键字:

在链表中间添加节点