image.png
1、查询操作
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
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;
}
}
可以看出LinkedList底层是链表操作，查询的时候采用二分查找法，通过for循环拿到值。效率低。
2、删除操作：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
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;
}
可以得知它是把上下两个节点连接起来了，效率较高（其实，这里在删除前也需要先循环查询到对应的节点，然后再进行删除操作。但是相比ArrayList需要移动数组，效率还是高的。）
3、修改操作
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
可以得到，只需要把item的引用变一下就可以了，但是修改之前需要先查询index处的节点，所以相较ArrayList效率低。
4、增加操作
public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}
可以得知，只需要改变最后一个节点的引用即可，效率高！
总结：查询修改效率低，增加删除效率高。但是由于采用了二分查找法，如果查询的对象在链表头部或者尾部，查询修改的效率也高！
模拟底层链表实现
package com.yidu.demo;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Set;
import java.util.TreeMap;
import java.util.Vector;
import org.omg.Messaging.SyncScopeHelper;
/**
* 模拟数组集合(底层数组实现)
* @author Administrator
*/
public class Array{
private Node first;//存储第一个节点
private Node last;//存储最后一个节点
private int size;
public void add(Object obj){
//如果是一个值
if(first==null){
//创建一个节点
Node n=new Node();
//因为它是第一个节点那么它没有上一个节点，也没有下一个节点
n.next=null;
n.prev=null;
n.obj=obj;
//因为它是第一个节点那么它既是第一个节点，也是最后一个节点
first=n;
last=n;
}else{
//创建一个节点
Node n=new Node();
n.next=null;
n.prev=last;
n.obj=obj;
last.next=n;
last=n;
}
size++;
}
public Object get(int index){
rangeCheck(index);
Node temp = node(index);
return temp.obj;
}
public void remove(int index){
rangeCheck(index);
Node temp = node(index);
Node up=temp.prev;
Node down=temp.next;
if(index!=0){
up.next=down;
}
if(index!=(size-1)){
down.prev=up;
}
size--;
};
public void set(int index,Object obj){
rangeCheck(index);
Node temp = node(index);
temp.obj=obj;
}
public void add(int index,Object obj){
if(index!=size-1){
rangeCheck(index);
Node temp = node(index);
Node n=new Node();
n.prev=temp;
n.next=temp.next;
n.obj=obj;
Node down=temp.next;
down.prev=n;
temp.next=n;
size++;
}else{
add(obj);
}
}
public Node node(int index){
Node temp=first;
for (int i = 0; i < index; i++) {
temp=temp.next;
}
return temp;
}
private void rangeCheck(int index){
if(index>=size||index<0){
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
}
public static void main(String[] args) {
Array a=new Array();
a.add("aaa");
a.add("ccc");
a.add(1,"bbb");
System.out.println(a.get(0));
System.out.println(a.get(1));
System.out.println(a.get(2));
}
}
class Node{
Node prev; //存储上一个node
Object obj; //存储值
Node next; //存储下一个node
public Node(Node prev, Object obj, Node next) {
super();
this.prev = prev;
this.obj = obj;
this.next = next;
}
public Node() {
super();
}
}
2019-01-12
