精华内容
下载资源
问答
  • Write code to remove duplicates from an unsorted linked list. FOLLOW UP How would you solve this problem if a temporary buffer is not allowed? ...soln: 还有就是快指针慢指针,不说了 ...

    Write code to remove duplicates from an unsorted linked list.
    FOLLOW UP
    How would you solve this problem if a temporary buffer is not allowed?


    soln: 还有就是快指针慢指针,不说了

    package test;



    import java.util.Scanner;
    import java.util.HashSet;
     
    public class JumpTwo {


        static class Node {
            char data;
            Node next = null;


            Node(char a) {
                this.data = a;
            }
        }


        public static void main(String[] args) {
     
            Egg egg = new Egg();
            Scanner input = new Scanner(System.in);
            StringBuffer sb = new StringBuffer(input.nextLine());
            String s = sb.toString();
            char[] chars = s.toCharArray();


            Node p = new Node('1');
            Node head = p;
            for (char c : chars) {
                    p.next = new Node(c);
                    p = p.next;
            }
            head = head.next;
            removeDup(head);
            while (null != head){
                System.out.println(head.data);
                head = head.next;
            }
        }


        private static void removeDup(Node head) {
            HashSet<Character> elem = new HashSet<Character>();
            Node cur = head.next;
            Node pre = head;
            elem.add(head.data);
            while (cur != null) {
                if (elem.contains(cur.data)) {
                    pre.next = cur.next;
                    cur = null;
                    cur = pre.next;
                } else {
                    elem.add(cur.data);
                    pre = cur;
                    cur = cur.next;
                }
            }
        }
    }
    展开全文
  • 创建链表LinkedList

    2017-04-24 20:16:00
    链表是由若干个节点的对象组成的一种数据结构分为单链表和双链表。...使用Java.util包中的LinkedList类可以创建一个链表对象 例如 LinkedList mylist=new LinkedList();//创建一个空双链表 ...

    链表是由若干个节点的对象组成的一种数据结构分为单链表和双链表。

    单链表:每个节点含有一个数据和下一个节点对象的引用。

    双链表:每个节点含有一个数据并含有上一个节点对象的引用和下一个节点对象的引用。

    创建链表

    使用Java.util包中的LinkedList类可以创建一个链表对象

    例如

    LinkedList mylist=new LinkedList();//创建一个空双链表

    可以使用add方法向链表依次增加节点

    例如

    mylist.add("加入的数据");

     mylist可以使用方法public Object get(index i)获取第i个节点中储存的数据。存放在节点中的数据都被看作一个Object对象。

     

    例:构造一个链表并输出节点中的数据

    import java.util.LinkedList;
    
    public class LinkListOne {
        public static void main(String[] args){
            LinkedList mylist = new LinkedList();//创建空链表
            mylist.add("a");//增加节点,第一节点
            mylist.add("b");//第二个节点
            mylist.add("c");
            mylist.add("d");
            mylist.add("e");
            int number =mylist.size();//获取节点的长度
            for(int i=0;i<number;i++){
                String temp = (String) mylist.get(i);//获取节点内数据
                System.out.println("第"+i+"节点数据:"+temp);
            }
            
        }
    
    }

    执行结果

    第0节点数据:a
    第1节点数据:b
    第2节点数据:c
    第3节点数据:d
    第4节点数据:e

     

     
     
     
    好文要顶 关注我 

    转载于:https://www.cnblogs.com/gc56-db/p/6758834.html

    展开全文
  • 创建LinkedList对象,从这里开始 0、无参 public LinkedList() { } 默认的构造方法,是我们最常用的,它只是new了一个对象 1、一个参数,接受一个Collection对象 public LinkedList(Collection<? ...

    (注意:本文源码基于JDK1.8) 

    创建LinkedList对象,从构造方法开始,接下来就分析这两个构造方法

     

    无参构造方法分析

        public LinkedList() {
        }

    默认无参构造方法是我们最常用的,它只是new了一个LinkedList对象,方法体中什么也没有做。注意:隐式的执行了super()调用基类的构造方法!

     

    传入一个参数的构造方法分析

        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }

    首先调用无参的构造方法,目的就是为了显式调用父类的构造方法,接着调用一个addAll方法(见添加元素文章中的详细分析),并将传入的Collection对象c传入进去!

     

    重要字段介绍

    1、继承父类的实例变量modCount

    用于fail-fast机制检测

    2、三个主要的实例变量+一个常量

    transient int size = 0;   
    transient Node<E> first; 
    transient Node<E> last;
    private static final long serialVersionUID = 876323262645176354L;

    size:表示LinkedList对象持有的元素总数,该实例变量使用transient修饰,不参与对象序列化

    first:表示LinkedList对象持有的第一个结点对象,不参与对象序列化

    last:表示LinkedList对象持有的最后一个结点对象,不参与对象序列化

    serialVersionUID:一个常量值,反序列化时,JVM用该UID与加载的类的UID作对比,两个值一致才会进行反序列化

     

    总结

    1、LinkedList基于持有的双向链表,LinkedList对象持有表示双向链表头结点对象的引用,实例变量first指向此Node对象

    2、LinkedList也持有表示双向链表尾结点对象的引用,实例变量last指向此Node对象

    3、LinkedList的父类为AbstractList,与ArrayList是同一个父类,实例变量modCount就定义在AbstractList类中

    展开全文
  • LinkedList源码分析

    2020-05-10 19:09:06
    ArrayList与LinkedList的区别在于: ArrayList内部使用数组进行实现 LinkedList内部使用链表进行实现 若对于ArrayList的实现原理还未...创建 LinkedList() public LinkedList() { } 无任何操作 LinkedList(C...

    ArrayListLinkedList的区别在于:

    • ArrayList内部使用数组进行实现
    • LinkedList内部实现方式:
      • 使用链表进行实现
      • 双向链表,即一个节点会记录前一个节点的位置和下个节点的位置
      • 记录首节点的位置以及尾结点的位置

    若对于ArrayList的实现原理还未了解,可以先看看ArrayList源码解析

    下面我们来分析下LinkedList里面常用方法的源码分析

    创建

    LinkedList()

        public LinkedList() {
        }
    

    无任何操作

    LinkedList(Collection<? extends E> c)

        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }
    
        public boolean addAll(Collection<? extends E> c) {
        	//size为当前的容量,默认添加到尾部
            return addAll(size, c);
        }
    
        public boolean addAll(int index, Collection<? extends E> c) {
        	//判断该下标是否越界
            checkPositionIndex(index);
    		
            Object[] a = c.toArray();
            int numNew = a.length;
            //无数据,添加失败
            if (numNew == 0)
                return false;
    		//pred为插入位置的前一个节点,succ为插入size下标位置的节点
            Node<E> pred, succ;
            if (index == size) {
                succ = null;
                pred = last;
            } else {
            	//获取下标位置的节点
                succ = node(index);
                pred = succ.prev;
            }
    
            for (Object o : a) {
                @SuppressWarnings("unchecked") E e = (E) o;
                //将Collection的每个数据都转换为一个节点
                Node<E> newNode = new Node<>(pred, e, null);
                if (pred == null)
                	//设置首节点
                    first = newNode;
                else
                	//将新节点插入尾部
                    pred.next = newNode;
                //刷新新的尾结点
                pred = newNode;
            }
    
            if (succ == null) {
            	//直接记录尾结点
                last = pred;
            } else {
            	//这个适用于插入的数据在链表的中部,
            	//在新增节点的尾部接上之前size后面那块的数据(包括size下标)
                pred.next = succ;
                succ.prev = pred;
            }
    		//更新链表长度
            size += numNew;
            //modCount用于记录更改次数
            modCount++;
            return true;
        }
    
    	//获取下标节点
        Node<E> node(int index) {
            // assert isElementIndex(index);
    		//首先,对于 index 值进行判断,判断在 size 的前一半还是在后一半
    		//若是前一半,则通过头节点,一个个往后获取
            if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
            //若是后一半,则通过尾结点,一个个往前获取
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }
    
    	//判断下标的合理性
        private void checkPositionIndex(int index) {
            if (!isPositionIndex(index))
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        private boolean isPositionIndex(int index) {
            return index >= 0 && index <= size;
        }
    
    

    添加

    addFirst(E e)

    将数据插入到首节点

        public void addFirst(E e) {
            linkFirst(e);
        }
        
        private void linkFirst(E e) {
            final Node<E> f = first;
            final Node<E> newNode = new Node<>(null, e, f);
            first = newNode;
            if (f == null)
            	//链表只有一个数据,首节点和尾结点为同一个节点
                last = newNode;
            else
            	//在新建节点的尾部插入之前的链表
                f.prev = newNode;
            size++;
            modCount++;
        }
    

    addLast(E e)

    将数据插入到尾节点

        public void addLast(E e) {
            linkLast(e);
        }
    
        void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
            	//将新建的节点插入到链表尾部
                l.next = newNode;
            size++;
            modCount++;
        }
    

    add(E e)

    添加节点,直接调用addLast(E e)

        public boolean add(E e) {
            linkLast(e);
            return true;
        }
    

    addAll(Collection<? extends E> c)

    请查看LinkedList(Collection<? extends E> c)分析

    addAll(int index, Collection<? extends E> c)

    请查看LinkedList(Collection<? extends E> c)分析

    add(int index, E element)

    在链表中部插入数据

        public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
    	//主体思路和addAll(int index, Collection<? extends E> c)一样
    	//都是先拿到index下标位置的数据和它前一个位置的数据,然后再进行中间插入
        void linkBefore(E e, Node<E> succ) {
            // assert succ != null;
            final Node<E> pred = succ.prev;
            final Node<E> newNode = new Node<>(pred, e, succ);
            succ.prev = newNode;
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            size++;
            modCount++;
        }
    

    删除

    removeFirst()

    移除首部节点,并且返回首节点的值

        public E removeFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
        }
    
        private E unlinkFirst(Node<E> f) {
            // assert f == first && f != null;
            final E element = f.item;
            final Node<E> next = f.next;
            //将首节点的内容以及其对下个节点的指向都置为null,便于资源回收
            f.item = null;
            f.next = null; // help GC
            //重新指向首节点,并且更新首节点或者尾结点的状态
            first = next;
            if (next == null)
                last = null;
            else
                next.prev = null;
            size--;
            modCount++;
            return element;
        }
    

    removeLast()

    移除尾结点,并且返回尾结点的值

        public E removeLast() {
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return unlinkLast(l);
        }
    	//原理跟unlinkFirst(Node<E> f) 类似,只是把对首节点的操作改为尾结点而已
        private E unlinkLast(Node<E> l) {
            // assert l == last && l != null;
            final E element = l.item;
            final Node<E> prev = l.prev;
            l.item = null;
            l.prev = null; // help GC
            last = prev;
            if (prev == null)
                first = null;
            else
                prev.next = null;
            size--;
            modCount++;
            return element;
        }
    

    remove(Object o)

    删除某个值

        public boolean remove(Object o) {
        	//从首节点开始一直遍历,直到找到相对应的值,并将其移除
            if (o == null) {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null) {
                        unlink(x);
                        return true;
                    }
                }
            } else {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item)) {
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
        }
    	//主要思路为:获取移除节点的上个节点和下个节点,将上节点之间指向下节点
        E unlink(Node<E> x) {
            // assert x != null;
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
    		//判断要移除的节点是不是首节点
            if (prev == null) {
                first = next;
            } else {
                prev.next = next;
                x.prev = null;
            }
    		//判断要移除的节点是不是尾结点
            if (next == null) {
                last = prev;
            } else {
                next.prev = prev;
                x.next = null;
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
        }
    
    

    remove(int index)

    移除某个下标值

        public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }
        //判断下标是否越界
        private void checkElementIndex(int index) {
            if (!isElementIndex(index))
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    

    remove()

    默认移除首节点

        public E remove() {
            return removeFirst();
        }
    

    set(int index, E element)

    给 index 下标赋新值

        public E set(int index, E element) {
            checkElementIndex(index);
            Node<E> x = node(index);
            E oldVal = x.item;
            x.item = element;
            return oldVal;
        }
    

    getFirst()

    获取第一个节点值

        public E getFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return f.item;
        }
    

    getLast()

    获取最后一个节点值

        public E getLast() {
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return l.item;
        }
    

    get(int index)

    获取index下标的节点值

        public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }
    

    indexOf(Object o)

    获取值的下标(从首部开始遍历)

    	//从头到尾依次遍历,若值相等,则返回相应下标
        public int indexOf(Object o) {
            int index = 0;
            if (o == null) {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null)
                        return index;
                    index++;
                }
            } else {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item))
                        return index;
                    index++;
                }
            }
            return -1;
        }
    

    lastIndexOf(Object o)

    获取值的下标(从尾部开始遍历)

        public int lastIndexOf(Object o) {
            int index = size;
            if (o == null) {
                for (Node<E> x = last; x != null; x = x.prev) {
                    index--;
                    if (x.item == null)
                        return index;
                }
            } else {
                for (Node<E> x = last; x != null; x = x.prev) {
                    index--;
                    if (o.equals(x.item))
                        return index;
                }
            }
            return -1;
        }
    

    contains(Object o)

    是否包含某值

        public boolean contains(Object o) {
            return indexOf(o) != -1;
        }
    

    其它

    size()

        public int size() {
            return size;
        }
    
    展开全文
  • LinkedList

    2020-05-10 19:44:08
    一、LinkedList介绍 LinkedList实现了链表的数据结构,链式结构使得LinkedList相对于顺序结构的ArrayList来说,在列表中插入数据或删除数据时效率更高。它实现了List接口并继承于AbstractSequentialList。构造方法...
  • LinkedList特点和常用操作

    千次阅读 2019-12-27 10:55:17
    创建LinkedList2.访问LinkedList3.Iterator遍历4.forEach 遍历 一、在线API 在线API 二、特点 LinkedList实现了Queue、Deque接口,; ArrayList适合删除操作,因为删除不会发生移位; ArrayList可以包含重复的元素...
  • LinkedList底层源码分析

    2019-09-03 20:06:34
    //在创建LinkedList对象时,只是加载了first和last普通的属性(赋值为null) transient Node<E> first; transient Node<E> last; /** * Pointer to last node. * Invariant: (first == null...
  • LinkedList集合 implements List接口 特点: ...1.创建LinkedList集合对象 LinkedList<String> linkedList=new LinkedList<>(); //往集合中添加元素 linkedList.add("a"); linkedList.
  • LinkedList的实现方式

    2019-08-06 20:10:07
    LinkedList是基于双向链表机制,所谓双向链表机制,就是集合中的每个元素都知道其前一个元素和其后的一个元素的位置LinkedList中,以一个内部的Entry类来代表集合中的元素,元素赋值给element...在创建LinkedList对...
  • 【Java】LinkedList集合

    2020-04-21 12:12:26
    LinkedList集合 底层是链表实现的 增删快、查询慢 --------------------------------------------- public class Demo { ... //创建LinkedList集合对象 LinkedList<String> list = new Li...
  • linkedlist

    2019-09-26 04:39:31
    1.ArrayList  去除ArrayList中重复字符串元素方式  同一个循环中,不能有两个next()方法,否则数据会丢失 ...创建一个新集合, 4 * 2.使用迭代器,把原集合的元素添加进新集合, 5 ...
  • 首先创建LinkedList并塞入数据LinkedList&lt;String&gt; list = new LinkedList&lt;&gt;(); list.add("James"); list.add("Irving"); list.addFirst("Curry"); ...
  • 用LinkedList模拟栈数据结构的集合并测试 A:案例演示 需求:请用LinkedList模拟栈数据结构的集合,并测试 创建一个类将Linked中的方法封装 ... //创建LinkedList对象 public void in(Obje...
  • java笔记之集合Collection集合定义通用方法ArrayList定义创建ArrayList对象ArrayList的常用方法LinkedList定义创建LinkedList对象LinkedList的独有方法SetHashSet使用Iterator迭代器遍历HashSet获取到迭代器对象...
  • Java集合----LinkedList

    2020-06-11 07:57:30
    浅谈LinkedList 首先呢我们来说说何为LinkedList,通过这个名字呢,我们不难看出,这是啷个单词的合成词,也就是Link 和List,别纠结我为什么不说是Linked好吧!...集合元素的创建 LinkedList list = new LinkedLi
  • 双向链表 双向类表的基本单元还是节点Node,每个节点都有三个属性:1、存储的数据 2、下一个节点的地址3、上一个...我们创建LinkedList对象后对其进行add操作本质是调用了底层的linkLast方法 void linkLast(E e) {
  • LinkedList集合

    2020-11-09 08:54:54
    一、LinkedList集合 java.util.LinkedList集合是java.util.List的实现类,实现List接口的所有方法(添加,删除,查找,判断是空等) ,它添加,删除元素... 其中必须通过LinkedList的引用创建该对象 public void addFirst
  • 创建一个linkedlist作为容器,数据源定义在main方法中 写出一下方法: 1.录入5条工人信息 2.输出所有工人信息 3.根据工人的id通过匿名内部类进行排序,并且输出,要求工人的排序不影响源数据顺序 通过存放在一个新的...
  • 前提:引入java.util包语法结构:相比叫ArrayList集合类,LinkedList更加灵活,在它基础上新增了头和尾的操作,比如从开头增加,从开头删除等等创建LinkedList类:LinkedList &lt;类型&gt; 集合名=new ...
  • 编写一个应用程序,要求将LinkedList创建的对象写入文件,在读出一个LinkedList节点中的数据。 import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; ...
  • 创建 LinkedList<Integer> list = new LinkedList<Integer>(); 添加元素:add或offer方法 list.add(1); list.add(2); 获取值:get方法,传入访问元素的下标 list.get(index); 移除元素:remove...
  • LinkedList基础

    2017-07-04 11:51:00
    好久没用LinkedList,发现好多基础的东西都不会了,所以特别写这篇来总结一下关于LinkedList的基本用法。 java.util ... 创建一个空的链表。 publicLinkedList(Collection<? extends E> c);...
  • linkedList:这是为odin项目课程使用OOP为ruby创建的链接列表

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,706
精华内容 682
关键字:

创建linkedlist