找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

微信名称:美国米群网

微 信 号:MeetQun

微信QQ:群: 320065698

查看: 339|回复: 3
收起左侧

[刷题总结] 对于LinkedList的总结

[复制链接]

8

主题

2

精华

55

积分

米群网会员

Rank: 2

积分
55
发表于 11-25-2016 12:19 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
刷题时经查会用到LinkedList这个数据结构,现将有关LinkedList的知识总结如下:在介绍LinkedList之前,我先来介绍下Collection,即集合,它是保存多个其他对象的对象,注意,它不能保存简单类型。
Collection框架(属于java.util包):
1.List
   LinkedList、ArrayList、Vector
2.Set
    HashSet、TreeSet
3.Map
   HashMap、Hashtable、WeakHashMap

该文主要针对LinkedList做一个总结。
LinkedList的特点是底层是用双向循环链表来实现的,查询效率低,但增删效率高,适用于增删比较频繁,查询次数较少的元素管理集合。

在Collection中有很多方法,包括add,addAll,clear,remove,removeAll,contains,containsAll,equals,isEmpty,size等,而LinkedList除了具有以上方法外 ,还有自己独有的方法:
addFirst();  
addLast();
getFirst();//获取元素但不删除
getLast();
removeFirst();//获取并删除元素,如果集合中没有元素会出现NoSuchElementException
removeLast();
//在jdk 1.6出现替代方法:
offerFirst();//在此列表开头插入指定元素
offerLast();
peekFirst();//获取但不删除列表中的第一个元素,如此列表为空,则返回null
peekLast();
pollFirst();//获取并删除元素。如果集合中没有元素不会出现NoSuchElementException,而会返回null
pollLast();
下面给出一些运用到链表的列子:
e.g 1 用LinkedList模拟一个队列(先进先出)
class Queue{
   private LinkedList<String> link;
   Queue(){
     link=new LinkedList<String>();
  }
  public void myAdd(String s){
       link.addFirst(s);
  }
  public String myGet(){
        return link.removeLast();
  }
   public boolean isNull(){
      return link.isEmpty();
}
}
e.g 2 Reverse a singly linked list
给个链表:7->14->21->28->null
反转后结果为: 28->21->14->7->null
该题我用两种方法来做,
解法一: iterative  Time :O(n)  Space O(1)
     class LinkedListNode{
         int data;
        LinkedListNode next;
        LinkedListNode(int data){this.data=data;}
  }
   LinkedListNode reverseIterative(LinkedListNode head){
         if(head==null || head.next==null)
                return head;
        LinkedListNode lk=head.next;
        LinkedListNode reversed=head;
        reversed.next=null;
        while(lk!=null){
            LinkedListNode temp=lk;
             lk=lk.next;
            temp.next=reversed;
            reversed=temp;
  }
    return reversed;
}
解法二:recursive  Time: O(n)  ,Space O(n)
  LinkedListNode reverseRecursive(LinkedListNode head){
         if(head==null || head.next==null)
                return head;
       LinkedListNode reversed= reverseRecursive(head.next);
       head.next.next=head;
      head.next=null;
      return reversed;
}
注意:对于解法二若是遇到很长的链表,有可能会ran out of memory.


0

主题

0

精华

8

积分

新米人

Rank: 1

积分
8
发表于 11-25-2016 12:19 AM 来自美国米群网手机版 | 显示全部楼层
感谢kathytree85分享~~~
回复 支持 反对

使用道具 举报

0

主题

0

精华

1

积分

新米人

Rank: 1

积分
1
发表于 11-25-2016 03:03 AM | 显示全部楼层
感谢kathytree85分享~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表