Java集合Collection之实现原理解读(LinkedList)
一、简介
LinkedList与ArrayList一样都实现了List接口，不过LinkedList底层实现是双向链表，对于插入、修改、删除速度比较快，对于查询就比较慢，因为要循环遍历查找。本章将模仿LinkedList源码实现一个简单的自定义LinkedList，以帮助饿哦们理解LinkedList底层是怎么实现的。
二、实现原理
LinkedList底层是通过双向链表实现的，通过一系列的节点Node串成一条链结构，一般操作思想就是找到索引对应的元素，找到前一节点previous和后一节点next，然后使其串起来一条链结构。
三、自定义LinkedList
package wsh.linkedlist;
/**
* 节点类
*
* @author weishihuai
* @date 2018/9/26 21:14
*/
public class Node {
/**
* 前一个节点
*/
private Node previous;
/**
* 下一个节点
*/
private Node next;
/**
* 当前节点的值
*/
private Object object;
public Node() {
}
public Node(Node previous, Node next, Object object) {
this.previous = previous;
this.next = next;
this.object = object;
}
public Node getPrevious() {
return previous;
}
public void setPrevious(Node previous) {
this.previous = previous;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Object getObject() {
return object;
}
public void setObject(Object object) {
this.object = object;
}
}
package wsh.linkedlist;
/**
* 自定义LinkedList,帮助理解底层实现
*
* @author weishihuai
* @date 2018/9/26 21:14
* <p>
* 说明:
* 1. LinkedList底层实现是双向链表,插入、修改、删除快，查询慢
* 2. 基本操作的思想: 找到索引对应的元素，找到前一节点和后一节点，然后串起来一条链。
*/
public class CustomLinkedList {
/**
* 第一个节点
*/
private Node first;
/**
* 最后一个节点
*/
private Node last;
/**
* 链表长度
*/
private int size;
/**
* 新增一个元素
*
* @param object 对象
*/
public void add(Object object) {
//如果第一个节点为空，说明为空链表
if (null == first) {
//创建一个新节点，赋值给first、last
Node node = new Node();
node.setPrevious(null);
node.setNext(null);
node.setObject(object);
//新创建的节点既是第一个节点，也是最后一个节点
first = node;
last = node;
} else {
//直接在last后面添加一个新的节点
Node node = new Node();
node.setPrevious(last);
node.setObject(object);
node.setNext(null);
//串成一条链
last.setNext(node);
//新创建的节点变成最后一个节点
last = node;
}
//每新增一个节点，长度需要加1
size++;
}
/**
* 获取LinkedList的长度
*
* @return LinkedList的长度
*/
public int size() {
return size;
}
/**
* 获取指定位置的元素
* 原理: 从第一个节点开始，循环遍历节点，temp = temp.getNext()
*
* @param index 索引
* @return 元素的值
*/
public Object get(int index) {
//判断索引是否越界
if (index < 0 || index >= size) {
throw new IllegalArgumentException("下标越界.....");
}
Node temp = null;
if (null != first) {
//0 1 2 3 4 5
temp = first;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
}
return null != temp ? temp.getObject() : null;
}
/**
* 删除指定索引的元素
* 原理: 找到指定下标所对应的元素，找出该节点对应的上一个节点和下一个节点，把上一个节点的next指向下一个节点，下一个节点的previous指向上一个节点，这样就跳过了该节点，达到 删除的效果。
*
* @param index 索引
*/
public void remove(int index) {
//判断索引是否越界
if (index < 0 || index >= size) {
throw new IllegalArgumentException("下标越界.....");
}
Node temp = null;
if (null != first) {
//0 1 2 3 4 5
temp = first;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
}
if (null != temp) {
Node previous = temp.getPrevious();
Node next = temp.getNext();
previous.setNext(next);
if (null != next) {
next.setPrevious(previous);
}
size--;
}
}
/**
* 指定位置插入对象
* 原理: 找到指定位置的元素，接着找到该节点对应的上一个节点，新建一个节点，用于连接之前的前后节点的桥梁
*
* @param index 索引
* @param object 对象
*/
public void add(int index, Object object) {
//判断索引是否越界
if (index < 0 || index >= size) {
throw new IllegalArgumentException("下标越界.....");
}
Node temp = null;
if (null != first) {
//0 1 2 3 4 5
temp = first;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
}
Node newNode = new Node();
newNode.setObject(object);
if (null != temp) {
Node previous = temp.getPrevious();
previous.setNext(newNode);
newNode.setPrevious(previous);
newNode.setNext(temp);
temp.setPrevious(newNode);
size++;
}
}
public Node getFirst() {
return first;
}
public void setFirst(Node first) {
this.first = first;
}
public Node getLast() {
return last;
}
public void setLast(Node last) {
this.last = last;
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
}
四、部分方法详解
【a】Node节点类
1. 节点类主要包含上一节点、下一节点以及当前节点的值
/**
* 前一个节点
*/
private Node previous;
/**
* 下一个节点
*/
private Node next;
/**
* 当前节点的值
*/
private Object object;【b】add(Object object) {} 往链表中插入元素
1. 实现原理:
a. 如果第一个节点为空，说明是一个空链表，那么需要创建一个新的节点，这个节点既是首节点，也是尾节点，
b. 如果第一个节点不为空，说明链表已经存在元素，那么只需要在当前last最后一个元素后面插入新创建的节点，并且把当前最后一个节点指定为新创建的节点(最新插入的节点变成最后一个节点)。
2. 注意每新插入一个元素，list的长度需要加1。
【c】get(int index) {} 获取指定索引对应的元素的值
1. 实现原理： 循环index次，定义一个临时变量temp,第一次从首节点开始查找，循环index次，执行temp = temp.getNext()
即循环将下一个节点赋值给temp,直到循环结束，就会找到相应的元素，返回其值。如果没找到返回null。
2. 注意需要判断索引是否合法。
【d】remove(int index) {} 删除指定索引的元素
1. 实现原理： 找到指定下标所对应的元素，找出该节点对应的上一个节点和下一个节点，把上一个节点的next指向下一个节点，下一个节点的previous指向上一个节点，这样就跳过了该节点，达到 删除的效果。
2. 注意需要判断索引是否合法
【e】add(int index, Object object) {} 往指定位置插入相应的元素
1. 实现原理: 找到指定位置的元素，接着找到该节点对应的上一个节点，新建一个节点，用于连接之前的前后节点的桥梁.
2. 注意需要判断索引是否合法
五、测试
package wsh.linkedlist;
/**
* 测试
*
* @author weishihuai
* @date 2018/9/26 21:19
*/
public class TestCustomLinkedList {
public static void main(String[] args) {
CustomLinkedList customLinkedList = new CustomLinkedList();
/***********************************add(object)***************************************/
customLinkedList.add("aaa");
customLinkedList.add("bbb");
customLinkedList.add("ccc");
/***********************************size()********************************************/
//3
System.out.println(customLinkedList.size());
/***********************************get(index)****************************************/
//bbb
System.out.println(customLinkedList.get(1));
//越界: java.lang.NullPointerException
//System.out.println(customLinkedList.get(3));
/***********************************remove(index)*************************************/
//3
System.out.println(customLinkedList.size());
customLinkedList.remove(2);
//2
System.out.println(customLinkedList.size());
/***********************************add(index,object)********************************/
customLinkedList.add(1, "ddd");
for (int i = 0; i < customLinkedList.size(); i++) {
//aaa ddd bbb
System.out.println(customLinkedList.get(i));
}
}
}
六、总结
以上就是关于LinkedList底层实现的一些基础原理，当然很多细节没考虑到，主要是能够帮助我们理解LinkedList底层是通过操作链表结构来实现数据的操作，简单理解就是找到索引对应的元素，然后找到上一节点以及下一节点，思想就是怎么把这些节点串成一条链结构，可以结合画图来理解一下。本文是作者的一些总结以及方法，仅供大家参考学习，一起学习一起进步。