概述
LinkedList
主要 特性：
顺序访问
写快读慢 读的时候需要遍历 底层采用了折半查找提高了效率 但是比起数组来说还是慢的多
查看源码
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
AbstractSequentialList：该抽象类继承自java.util.AbstractList 提供了顺序访问存储结构，只要类似于linkedList这样的顺序访问List 都可以继承该类
List：列表标准接口，列表是一个有序集合，又被称为序列，该接口对内部的每一个元素的插入位置都有精确控制
Deque：双向队列接口，继承自Queue 因为Queue是先进先出的特性 继承后 就看可以在尾部增加数据头部获取数据
Cloneable：标记可克隆对象 ，没有实现该接口的对象在调用Object.clone()方法时会抛出异常 分为浅拷贝和深拷贝 这里默认都是浅拷贝
java.io.Serializable：序列化标记接口 被此接口标记的类 可以实现Java序列化和反序列化
手写内容
成员变量和常量
size标记序列的大小 统计节点的个数
first 链表的头结点
last 链表的尾结点
/**
* 链表实际长度
*/
private int size;
/**
* 指向第一个节点 为了查询开始
*/
private Node first;
/**
* 指向最后一个节点 为了插入开始
*/
private Node last;
这里没有和源码一样用transient修饰
transient修饰 的作用是 用于标记无需序列化的成员变量
也就是说 实现了 Serializable接口的LinkedList 一定提供了readObject和writeObject方法 源码如下
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
/**
* Reconstitutes this {@code LinkedList} instance from a stream
* (that is, deserializes it).
*/
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}
Node节点
链表由节点构成 节点又包含 数据域 和指针域
prev 前指针
next 后指针
object就是数据域
class Node{
/**
* 前指针 指向上一个节点
*/
Node prev;
/**
* 后指针 指向下一个节点
*/
Node next;
Object object;
}
add方法
创建一个节点 将插入的数据给这个节点的数据域赋值
判断头指针是否为空 为空则说明这个是头指针 不为空则在尾部进行插入
然后让这个节点为最后一个节点
链表长度+1
主要逻辑详见注解
/**
* 添加数据进入
* @param e
*/
public void add(E e){
Node node = new Node();
node.object = e;
//如果第一个节点为空 就插入第一个数据
if(first == null){
//添加第一个元素给第一个元素赋值
first = node;
}else{//插入第二个及其以上数据
node.prev = last;
//将上一个元素的节点的下一个指向node 此时node还不是last
last.next = node;
}
last = node;
size++;
}
/**
* 插入节点
* @param index
* @param e
*/
public void add(int index, E e) {
Node newNode = new Node();
newNode.object = e;
// 获取原来的节点
Node oldNode = getNode(index);
// 获取原来的上一个节点
Node oldNodePrev = oldNode.prev;
//将原来的节点的上一个节点为新节点
oldNode.prev = newNode;
if (oldNodePrev == null) {
first = newNode;
} else {
//上一个节点的下一个节点是新节点
oldNodePrev.next = newNode;
}
//新节点的下一个节点为原来节点
newNode.next = oldNode;
size++;
}
get方法
源码是这样写的 采用折半查找进行数据的搜索
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;
}
}
我这里简单点 直接遍历查找获取
/**
* 获取元素值
* @param index
* @return
*/
public E get(int index) {
Node node = getNode(index);
return (E) node.object;
}
/**
* 得到节点
* @param index
* @return
*/
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;
}
set方法
数据的修改
调用前面的获取当前的节点的值get方法获取 然后直接修改值即可
/**
* 修改数据
* @param index
* @param element
* @return
*/
public E set(int index, E element) {
checkElementIndex(index);
Node node = getNode(index);
E oldVal = (E) node.object;
node.object = element;
return oldVal;
}
越界问题
判断是否越界 当前的索引必须大于0小于当前链表的长度
/**
* 检查越界
* @param index
*/
private void checkElementIndex(int index) {
if (!isElementIndex(index)) {
throw new IndexOutOfBoundsException("下标越界");
}
}
/**
* 判断参数是否是现有元素的索引
* @param index
* @return
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
remove方法
移除元素
判断越界问题
拿到当前要移除的节点
拿到当前要移除节点的上一个节点和下一个节点 方便把这两个节点连接在一块
连接上一个节点和下一个节点 判断边界
长度减1
/**
* 删除元素
* @param index
* @return
*/
public Object remove(int index){
//检查越界
checkElementIndex(index);
//获取当前删除节点
Node node = getNode(index);
if (node != null) {
//得到当前删除节点的上一个节点
Node prevNode = node.prev;
//得到当前删除节点的下一个节点
Node nextNode = node.next;
// 设置上一个节点的next为当前删除节点的next
if (prevNode != null) {
prevNode.next = nextNode;
}
// 判断是否是最后一个节点
if (nextNode != null) {
nextNode.prev = prevNode;
}
}
size--;
return node;
}
clear方法
循环清除整个链表
置为空后将垃圾回收交给垃圾回收器自己判断清除
链表长度置为1
public void clear(){
//循环清除各个节点之间的联系
for (Node x = first; x != null; ) {
Node next = x.next;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
}
完整代码
import java.util.LinkedList;
/**
* @author Yu W
* @version V1.0
* @ClassName MyLinkedList
* @Description: 手写LinkedList 学习LinkedList源码
* @date 2021/7/18 18:00
*/
public class MyLinkedList <E> {
class Node{
/**
* 前指针 指向上一个节点
*/
Node prev;
/**
* 后指针 指向下一个节点
*/
Node next;
Object object;
}
/**
* 链表实际长度
*/
private int size;
/**
* 指向第一个节点 为了查询开始
*/
private Node first;
/**
* 指向最后一个节点 为了插入开始
*/
private Node last;
/**
* 添加数据进入
* @param e
*/
public void add(E e){
Node node = new Node();
node.object = e;
//如果第一个节点为空 就插入第一个数据
if(first == null){
//添加第一个元素给第一个元素赋值
first = node;
}else{//插入第二个及其以上数据
node.prev = last;
//将上一个元素的节点的下一个指向node 此时node还不是last
last.next = node;
}
last = node;
size++;
}
/**
* 修改数据
* @param index
* @param element
* @return
*/
public E set(int index, E element) {
checkElementIndex(index);
Node node = getNode(index);
E oldVal = (E) node.object;
node.object = element;
return oldVal;
}
/**
* 插入节点
* @param index
* @param e
*/
public void add(int index, E e) {
Node newNode = new Node();
newNode.object = e;
// 获取原来的节点
Node oldNode = getNode(index);
// 获取原来的上一个节点
Node oldNodePrev = oldNode.prev;
//将原来的节点的上一个节点为新节点
oldNode.prev = newNode;
if (oldNodePrev == null) {
first = newNode;
} else {
//上一个节点的下一个节点是新节点
oldNodePrev.next = newNode;
}
//新节点的下一个节点为原来节点
newNode.next = oldNode;
size++;
}
/**
* 获取元素值
* @param index
* @return
*/
public E get(int index) {
Node node = getNode(index);
return (E) node.object;
}
/**
* 得到节点
* @param index
* @return
*/
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
*/
public Object remove(int index){
//检查越界
checkElementIndex(index);
//获取当前删除节点
Node node = getNode(index);
if (node != null) {
//得到当前删除节点的上一个节点
Node prevNode = node.prev;
//得到当前删除节点的下一个节点
Node nextNode = node.next;
// 设置上一个节点的next为当前删除节点的next
if (prevNode != null) {
prevNode.next = nextNode;
}
// 判断是否是最后一个节点
if (nextNode != null) {
nextNode.prev = prevNode;
}
}
size--;
return node;
}
/**
* 检查越界
* @param index
*/
private void checkElementIndex(int index) {
if (!isElementIndex(index)) {
throw new IndexOutOfBoundsException("下标越界");
}
}
/**
* 判断参数是否是现有元素的索引
* @param index
* @return
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/**
* 从此列表中删除所有元素。此调用返回后，列表将为空
*/
public void clear(){
//循环清除各个节点之间的联系
for (Node x = first; x != null; ) {
Node next = x.next;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
}
}
————————————————