Android-LinkedList

发表于   |   分类于   |  

前言

Linus Benedict Torvalds : RTFSC – Read The Funning Source Code

概述

LinkedList is an implementation of List, backed by a doubly-linked list. All optional operations including adding, removing, and replacing elements are supported. All elements are permitted, including null. This class is primarily useful if you need queue-like behavior. It may also be useful as a list if you expect your lists to contain zero or one element, but still require the ability to scale to slightly larger numbers of elements.

LinkedList的数据结构是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用。

1
2
3
4
5
6
7
8
9
10
11
private static final class Link<ET> {
    ET data;
    Link<ET> previous, next;
    Link(ET o, Link<ET> p, Link<ET> n) {
        data = o;
        previous = p;
        next = n;
    }
}

使用

1
2
3
4
5
6
7
8
9
LinkedList<String> lList = new LinkedList<String>(); 
lList.add("1"); 
lList.add("2"); 
lList.add("3"); 
lList.add("4"); 
lList.add("5");
                                                                                                                                                                                                                 
System.out.println("第一个元素是 :" + lList.getFirst()); 
System.out.println("最后一个元素是 :" + lList.getLast());

初始化

1
LinkedList<T> lList = new LinkedList<T>();

添加元素

1
2
3
4
5
public boolean add(Object element)
public boolean add(int index, Object element)
public boolean addFirst(Object element)
public boolean addLast(Object element)

删除元素

1
2
public E remove(int location)
public boolean remove(Object object)

查找元素

1
2
3
4
5
6
7
8
9
LinkedList<String> lList = new LinkedList<String>(); 
lList.add("1"); 
lList.add("2"); 
lList.add("3"); 
lList.add("4"); 
lList.add("5"); 
lList.add("2"); 
System.out.println(lList.indexOf("2")); 
System.out.println(lList.lastIndexOf("2"));

特性

优点

  1. 对于增加、删除、移动效率都非常高。因为改动只需要针对链表的前后节点。
  2. 因为是链表，对于内存来说是不连续的，空间利用率较高。

缺点

  1. 因为是链表结构，在查询上只能从头往后查找，对于效率来说十分低下。
  2. 因为是链表，对于内存来说是不连续的，在优化内存分配上不太友好。