自定义一个LinkedList
LinkedList特点和底层实现
LinkedList底层用双向链表实现的存储。特点:查询效率低,增删效率高,线程不安全。
双向链表也叫双链表,是链表的一种,它的每个数据节点中都有两个指针,分别指向前一个节点和后一个节点。 所以,从双向链表中的任意一个节点开始,都可以很方便地找到所有节点。下图为LinkedList的存储结构图:
每个节点都应该有3部分内容:
class Node {
Node previous; //前一个节点
Object element; //本节点保存的数据
Node next; //后一个节点
}
查看LinkedList的源码,可以看到里面包含了双向链表的相关代码:
自定义一个LinkedList,体会底层原理
代码如下:
package com.msl.mycollection;
/**
* 自定义实现一个链表
* @author Senley
*/
public class MslLinkedList<E> {
private Node first;
private Node last;
private int size;
public static void main(String[] args) {
MslLinkedList<String> list = new MslLinkedList();
list.add("a");
list.add("b");
list.add("c");
System.out.println(list);
System.out.println(list.get(2));
list.remove(0);
System.out.println(list);
list.add(1, "插入");
System.out.println(list);
}
public void add(int index,E element) {
checkRange(index);
Node newNode = new Node(element);
Node temp = getNode(index);
if(temp!=null) {
Node up = temp.previous;
up.next = newNode;
newNode.previous = up;
newNode.next = temp;
temp.previous = newNode;
}
}
public void remove(int index) {
checkRange(index);
Node temp = getNode(index);
if(temp!=null) {
Node up = temp.previous;
Node down = temp.next;
if(up!=null) {
up.next = down;
}
if(down!=null) {
down.previous = up;
}
//被删除的元素是第一个元素时
if(index==0) {
first = down;
}
//被删除的元素是最后一个元素时
if(index==size-1) {
last = up;
}
size--;
}
}
public void add(E element) {
Node node = new Node(element);
if(first==null) {
// node.previous = null;
// node.next = null;
first = node;
last = node;
}else {
node.previous = last;
node.next = null;
last.next = node;
last = node;
}
size++;
}
public E get(int index) {
checkRange(index);
Node temp = getNode(index);
return temp!=null?(E)temp.element:null;
}
private void checkRange(int index) {
if(index<0 || index>size-1) {
throw new RuntimeException("索引数字不合法:"+index);
}
}
private Node getNode(int index) {
checkRange(index);
Node temp = null;
if(index<=(size>>1)) {//size>>1相当于除以2
temp = first;
for(int i=0;i<index;i++) {
temp = temp.next;
}
}else {
temp = last;
for(int i=size-1;i>index;i--) {
temp = temp.previous;
}
}
return temp;
}
@Override
public String toString() {
//[a b c] first = a, last = c
StringBuilder sb = new StringBuilder("[");
Node temp = first;
while(temp!=null) {
sb.append(temp.element+",");
temp = temp.next;
}
sb.setCharAt(sb.length()-1, ']');
return sb.toString();
}
}
结果如下:
[a,b,c]
c
[b,c]
[b,插入,c]