比尔云BierYun--阿里云最新优惠活动
阿里云优惠码丨阿里云代金券

Java知识点总结(Java容器-LinkedList)

Java知识点总结(Java容器-LinkedList)

LinkedList

底层实现是双向循环链表,所以增删元素效率高,查询慢。线程安全

ArrayList和LinkedList比较

  1. ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构
  2. 对于水机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针
  3. 对于新增和删除操作add和remove,LinkedList比较占优势,因为ArrayList要移动数据

这一点要看实际情况的。若只对单条数据插入或删除,ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据,LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据,要移动插入点及之后的所有数据。

手写LinkedList

public  class MyLinkedList /*implements List<E>*/ {
  private Node first;
  private Node last;
  private int size ;
  
  //新增元素
  public void add(Object obj) {
    if (first == null) {
      Node n = new Node(null,obj,null);
      first = n;
      last = n;
    }else {
      //直接往last后增加新的节点
      Node n = new Node(last, obj, null);
      last.setNext(n);
      last = n;
    }
    size++;
  }
  
  //获取元素
  public Object get(int  index) throws Exception {
    return getNode(index).getObj();
  }
  //删除元素
  public boolean remove(int index) throws Exception {
    boolean flag = false;
    Node temp = getNode(index);
    if (temp!=null) {
      temp.getPreview().setNext(temp.getNext());
      temp.getNext().setPreview(temp.getPreview());
      size--;
      flag = true;
    }
    return flag;
  }
  //指定位置加入元素
  public boolean add(int index,Object obj) throws Exception {
    boolean flag = false;
    Node temp = getNode(index);
    if (temp!=null) {
      if (index == 0) {
        Node n = new Node(null,obj,temp);
        first = n;
      }else {
        Node n = new Node(temp.getPreview(),obj,temp);
        temp.getPreview().setNext(n);
        temp.setPreview(n);
      }     
      size++;
      flag = true;
    }
    return flag;
  }
  //替换节点
  public boolean set(int index,Object obj) throws Exception{
    boolean flag = false;
    Node temp = getNode(index);
    System.out.println("获取的节点" +temp.getObj()+temp.getPreview().getObj()+temp.getNext().getObj());
    if (temp!=null) {
      
      Node n = new Node(temp.getPreview(),obj,temp.getNext());
      temp.getPreview().setNext(n);
      temp.getNext().setPreview(n);
      flag = true;
    }
    return flag;
  }
  public int size(){
    return size;
  }
  
  public void rangeCheck(int index) throws Exception {
    if (index <0 || index > size) {
      throw new Exception();
    }
  }
  
  public Node getNode(int index) throws Exception {
    rangeCheck(index);
    Node temp = null;
    //if (first != null) {  
      /*for (int i = 0; i < index; i++) {
        temp = temp.getNext();
      }*/
      /*int i = 0;
      while(temp.getNext() != null && i<index){
        temp = temp.getNext();
        i++;
      }*/
    //}
     if (index  < (size >> 1)) {//向右移动一位,相当于/2
              temp = first;
              for (int i = 0; i < index; i++)
                  temp = temp.getNext();
              return temp;
          } else {
              temp = last;
              for (int i = size - 1; i > index; i--)
                 temp = temp.getPreview();
              return temp;
          }
  }
  public static void main(String[] args) throws Exception {
    MyLinkedList list = new MyLinkedList();
    list.add("a" );
    list.add("b" );
    list.add("c" );
    list.add("d" );
    list.add("e" );
    list.add("f" );
    System.out.println(list.size());
    list.remove(3);
    list.add(2, "新节点" );
    list.set(4, "替换");
    for (int i = 0; i <list.size(); i++) {
      System.out.println(list.get(i));
    }
  }
}
 
//定义一个内部类用来表示一个节点
class  Node{
  private Node preview;
  private Object obj;
  private Node next;
  public Node() {
    
  }
  public Node(Node preview, Object obj, Node next) {
    this();
    this.preview = preview;
    this.obj = obj;
    this.next = next;
  }
  public Node getPreview() {
    return preview;
  }
  public void setPreview(Node preview) {
    this.preview = preview;
  }
  public Object getObj() {
    return obj ;
  }
  public void setObj(Object obj) {
    this.obj = obj;
  }
  public Node getNext() {
    return next;
  }
  public void setNext(Node next) {
    this.next = next;
  }
}

未经允许不得转载:比尔云 » Java知识点总结(Java容器-LinkedList)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

强烈推荐

高性能SSD云服务器ECS抗攻击,高可用云数据库RDS