|
目录
1.LinkedList? 的源码研究
1，继承关系
2，构造函数
3，属性信息
4，底层数据结构
5，常用方法研究
2.LinkedList 方法的使用
1.LinkedList? 的源码研究
1，继承关系
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
/**
* LinkedList继承自 AbstractSequentialList类
* 实现了List，Deque, Cloneable, Serializable接口
* List接口是ArrayList、Linkedlist的接口，定义了集合中大部分方法
* Deque接口实现了Deque所有的可选的操作
* Cloneable接口表明当前类是可以被克隆
* Serializable接口表明当前类是可以支持序列化和反序列化
*/
2，构造函数
// 构造一个空列表
public LinkedList() {
}
// 通过集合实例来实例化LinkedList
public LinkedList(Collection<? extends E> c) {
this();
// 添加指定元素的列表
addAll(c);
}
3，属性信息
// 用来记录LinkedList的大小
transient int size = 0;
// 用来标记头节点
transient Node<E> first;
// 用来标记尾巴节点
transient Node<E> last;
4，底层数据结构
底层数据结构是双向链表。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
5，常用方法研究
add(E e)
// 默认添加到集合的末尾
public boolean add(E e) {
linkLast(e);
return true;
}
// 尾部添加
void linkLast(E e) {
// 标记尾巴节点
final Node<E> l = last;
// 添加新节点在尾部，前驱为l，后继为null
final Node<E> newNode = new Node<>(l, e, null);
//更新尾巴节点
last = newNode;
// 判断链表是否为空
if (l == null)
first = newNode;
else
l.next = newNode;
//LinkedList长度加1
size++;
modCount++;
}
addFirst(E e)
// 添加到集合的第一个位置
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
//前驱为null，后继为当前头节点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
// 判断LinkedList是否为空
if (f == null)
last = newNode;
else
f.prev = newNode;
//LinkedList长度加一
size++;
modCount++;
}
addLast(E e)
// 尾部添加
public void addLast(E e) {
// 在add（）方法已介绍
linkLast(e);
}
remove(Object o)
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;
}
// 修改该元素的前驱节点和后继节点
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;
// LinkedList长度减1；
size--;
modCount++;
return element;
}
set(int index, E element)
// 将此列表中指定位置的元素替换为指定的元素。
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
//得到要替换元素的值
E oldVal = x.item;
x.item = element;
return oldVal;
}
//异常
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 判断元素下标是否越界
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
contains(Object o)
// 判断是否包含元素 o
public boolean contains(Object o) {
// 返回值 != -1;则包含。
return indexOf(o) != -1;
}
// 查找相应元素并返回下标，若没有，返回-1
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
get(int index)
// 返回下标为 index 的元素
public E get(int index) {
// 安全检测
checkElementIndex(index);
return node(index).item;
}
size()
// 返回LinkedList的长度
public int size() {
return size;
}
2.LinkedList 方法的使用
?
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(4);
int size = linkedList.size();
System.out.println("linkedList的个数为："+size);
System.out.print("操作前的元素为：");
Iterator<Integer> iterator = linkedList.iterator();
while (iterator.hasNext()){
Integer value=iterator.next();
System.out.print(value+" ");
}
System.out.println("");
linkedList.remove(Integer.valueOf(1));
System.out.print("删除后的元素为：");
Iterator<Integer> iterator1 = linkedList.iterator();
while (iterator1.hasNext()){
Integer value1=iterator1.next();
System.out.print(value1+" ");
}
System.out.println("");
linkedList.set(1,5); // 2 5 4
System.out.print("修改后的元素为：");
Iterator<Integer> iterator2 = linkedList.iterator();
while (iterator2.hasNext()){
Integer value1=iterator2.next();
System.out.print(value1+" ");
}
System.out.println("");
boolean result = linkedList.contains(Integer.valueOf(2));
System.out.println(result);
}
|