十分钟带你分析 LinkedList 源码

LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据,既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息。

废话不多说，如果你有数据结构中关于链表的知识，那手写LinkedList根本不需要十分钟。源码就简单的罗列一下，其实源码就是用的链表的数据结构来实现的。

LinkedList源码

transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }
    
   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++;
    }
    
    public void add(int index, E element) {
    // 判断是否越界
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    
  public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
           

下面就直接上纯手写的LinkedList…

还是一步一步来介绍。思路都在注释上。

• 创建节点Node类

public class Node<E> {

	// 上一个节点
	public Node prev;
	// 节点内容
	public Object object;
	// 下一个节点
	public Node next;

}

           

• 书写构造方法，初始化头尾节点和链表大小

/**
	 * 当前链表真实长度
	 */
	private int size = 0;

	/**
	 * 第一个头节点
	 */
	private Node<E> first;

	/**
	 * 最后一个尾节点
	 */
	private Node<E> last;

	/**
	 * 构造方法
	 */
	public XLinkedList() {
	}

           

• 先来一个add方法

/**
	 * 默认在链表尾部进行元素添加
	 * 
	 * @param index
	 */
	public void add(E e) {
		Node<E> node = new Node<E>();
		node.object = e;
		/**
		 * 如果链接为空则在头添加 否则在尾部添加
		 */
		if (first == null) {
			first = node;
		} else {
			last.next = node;
			node.prev = last;
		}

		last = node;
		size++;

	}

           

• 再来一个按下标添加

/**
	 * 按下标位置进行add
	 * 
	 * @return
	 */
	public void add(int index, E e) {
		checkElementIndex(index);
		Node<E> newNode = new Node<E>();
		newNode.object = e;
		// 获取原来下标位置的节点
		Node oldNode = getNode(index);
		if (oldNode != null) {
			// 拿到前一个结点 node1
			Node prevNode = oldNode.prev;
			// 拿到后一个节点node3
			Node nextNode = oldNode.next;

			if (oldNode.prev == null) {
				first = newNode;
			} else {
				if (prevNode != null) {
					prevNode.next = newNode;
					newNode.prev = prevNode;

				}
				// 判断是否是最后一个节点
				if (nextNode != null) {
					nextNode.prev = oldNode;
					oldNode.next = newNode;
				}
			}
			newNode.next = oldNode;
			oldNode.prev = newNode;
			size++;
		}

	}
           

• 删除

  

/**
	 * 删除链表元素 1.首先进行越界判断
	 * 
	 * @return
	 */
	public void remove(int index) {
		checkElementIndex(index);
		// 拿到被删除位置的节点 假如叫node2 其存储结构为 node1-》node2-》node3
		Node node = getNode(index);
		if (node != null) {
			// 拿到前一个结点 node1
			Node prevNode = node.prev;
			// 拿到后一个节点node3
			Node nextNode = node.next;
			// 设置上一个节点的next为当前删除节点的next
			if (prevNode != null) {
				prevNode.next = nextNode;
				node = null;
			}

			// 判断是否是最后一个节点
			if (nextNode != null) {
				nextNode.prev = prevNode;
				node = null;
			}

		}
		size--;
	}
           

• 补充一些其他方法

获取元素：

/*
	 * 返回链表大小
	 */
	public int getSize() {
		return size;

	}

	/**
	 * 返回链接中元素
	 * 
	 * @param index
	 * @return
	 */
	public E get(int index) {
		Node node = getNode(index);
		return (E) node.object;
	}

	public Node getNode(int index) {
		Node node = null;
		if (first != null) {
			node = first;
			for (int i = 0; i < index; i++) {
				node = node.next;
			}
		}
		return node;
	}

	/**
	 * 越界判断
	 * 
	 * @param index
	 * @return
	 */
	private boolean isElementIndex(int index) {
		return index >= 0 && index < size;
	}

	private void checkElementIndex(int index) {
		if (!isElementIndex(index))
			throw new IndexOutOfBoundsException("越界啦!");
	}
           

• Mian方法调用

/**
 *  纯手写 LinkedList
 * @author 程序员快乐的秘密
 *
 */
public class MainTest {

	public static void main(String[] args) {
		// 先看看源码 学习一下源码
		LinkedList linkedList = new LinkedList();
		linkedList.add("xianglei");

		XLinkedList<String> xLinkedList = new XLinkedList<String>();
		xLinkedList.add("xianglei");
		xLinkedList.add("dengxinlei");
		xLinkedList.add("hahaha");
		xLinkedList.add(0, "welcome");
//		xLinkedList.remove(0);
		for (int i = 0; i < xLinkedList.getSize(); i++) {
			System.out.println(xLinkedList.get(i));
		}

	}

}

           

总结

链表存储和数组存储在本质上还是存在一定的区别：

• 存取方式上，数组可以顺序存取或者随机存取，而链表只能顺序存取；
• 存储位置上，数组逻辑上相邻的元素在物理存储位置上也相邻，而链表不一定；
• 存储空间上，链表由于带有指针域，存储密度不如数组大；
• 按序号查找时，数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，平均需要O(n)；
• 按值查找时，若数组无序，数组和链表时间复杂度均为O(1)，但是当数组有序时，可以采用折半查找将时间复杂度降为O(logn)；
• 插入和删除时，数组平均需要移动n/2个元素，而链表只需修改指针即可；

• 空间分配方面：

  　　数组在静态存储分配情形下，存储元素数量受限制，动态存储分配情形下，虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且如果内存中没有更大块连续存储空间将导致分配失败； 　

  　　链表存储的节点空间只在需要的时候申请分配，只要内存中有空间就可以分配，操作比较灵活高效；

• 数组从栈中分配空间, 对于程序员方便快速,但自由度小。
• 链表从堆中分配空间, 自由度大但申请管理比较麻烦.