LinkedList实现类的使用
一、实例使用
package com.lanson.test04;
import java.util.Iterator;
import java.util.LinkedList;
/**
* @author : lanson
*/
public class Test {
//这是main方法,程序的入口
public static void main(String[] args) {
/*
LinkedList常用方法:
增加 addFirst(E e) addLast(E e)
offer(E e) offerFirst(E e) offerLast(E e)
删除 poll()
pollFirst() pollLast() ---》JDK1.6以后新出的方法,提高了代码的健壮性
removeFirst() removeLast()
修改
查看 element()
getFirst() getLast()
indexOf(Object o) lastIndexOf(Object o)
peek()
peekFirst() peekLast()
判断
*/
//创建一个LinkedList集合对象:
LinkedList<String> list = new LinkedList<>();
list.add("aaaaa");
list.add("bbbbb");
list.add("ccccc");
list.add("ddddd");
list.add("eeeee");
list.add("bbbbb");
list.add("fffff");
list.addFirst("jj");
list.addLast("hh");
list.offer("kk");//添加元素在尾端
list.offerFirst("pp");
list.offerLast("rr");
System.out.println(list);//LinkedList可以添加重复数据
System.out.println(list.poll());//删除头上的元素并且将元素输出
System.out.println(list.pollFirst());
System.out.println(list.pollLast());
System.out.println(list.removeFirst());
System.out.println(list.removeLast());
System.out.println(list);//LinkedList可以添加重复数据
/*list.clear();//清空集合
System.out.println(list);*/
/*System.out.println(list.pollFirst());*/
/*System.out.println(list.removeFirst());报错:Exception in thread "main" java.util.NoSuchElementException*/
//集合的遍历:
System.out.println("---------------------");
//普通for循环:
for(int i = 0;i<list.size();i++){
System.out.println(list.get(i));
}
System.out.println("---------------------");
//增强for:
for(String s:list){
System.out.println(s);
}
System.out.println("---------------------");
//迭代器:
/*Iterator<String> it = list.iterator();
while(it.hasNext()){
System.out.println(it.next());
}*/
//下面这种方式好,节省内存
for(Iterator<String> it = list.iterator();it.hasNext();){
System.out.println(it.next());
}
}
}
二、LinkedList简要底层原理图
三、模拟LinkedList源码
package com.lanson.test05;
/**
* @author : lanson
*/
public class MyLinkedList {
//链中一定有一个首节点:
Node first;
//链中一定有一个尾节点:
Node last;
//计数器:
int count = 0;
//提供一个构造器:
public MyLinkedList(){
}
//添加元素方法:
public void add(Object o){
if(first == null){//证明你添加的元素是第一个节点:
//将添加的元素封装为一个Node对象:
Node n = new Node();
n.setPre(null);
n.setObj(o);
n.setNext(null);
//当前链中第一个节点变为n
first = n;
//当前链中最后一个节点变为n
last = n;
}else{//证明已经不是链中第一个节点了
//将添加的元素封装为一个Node对象:
Node n = new Node();
n.setPre(last);//n的上一个节点一定是当前链中的最后一个节点last
n.setObj(o);
n.setNext(null);
//当前链中的最后一个节点的下一个元素 要指向n
last.setNext(n);
//将最后一个节点变为n
last = n;
}
//链中元素数量加1
count++;
}
//得到集合中元素的数量:
public int getSize(){
return count;
}
//通过下标得到元素:
public Object get(int index){
//获取链表的头元素:
Node n = first;
//一路next得到想要的元素
for(int i=0;i<index;i++){
n = n.getNext();
}
return n.getObj();
}
}
class Test{
//这是main方法,程序的入口
public static void main(String[] args) {
//创建一个MyLinkedList集合对象:
MyLinkedList ml = new MyLinkedList();
ml.add("aa");
ml.add("bb");
ml.add("cc");
System.out.println(ml.getSize());
System.out.println(ml.get(0));
}
}
debug验证数据添加成功:
四、LinkedList源码解析
1、JDK1.7和JDK1.8的LinkedList的源码是一致的
2、源码:
public class LinkedList<E>{//E是一个泛型,具体的类型要在实例化的时候才会最终确定
transient int size = 0;//集合中元素的数量
//Node的内部类
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;
}
}
transient Node<E> first;//链表的首节点
transient Node<E> last;//链表的尾节点
//空构造器:
public LinkedList() {
}
//添加元素操作:
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {//添加的元素e
final Node<E> l = last;//将链表中的last节点给l 如果是第一个元素的话 l为null
//将元素封装为一个Node具体的对象:
final Node<E> newNode = new Node<>(l, e, null);
//将链表的last节点指向新的创建的对象:
last = newNode;
if (l == null)//如果添加的是第一个节点
first = newNode;//将链表的first节点指向为新节点
else//如果添加的不是第一个节点
l.next = newNode;//将l的下一个指向为新的节点
size++;//集合中元素数量加1操作
modCount++;
}
//获取集合中元素数量
public int size() {
return size;
}
//通过索引得到元素:
public E get(int index) {
checkElementIndex(index);//健壮性考虑
return node(index).item;
}
Node<E> node(int index) {
//如果index在链表的前半段,那么从前往后找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//如果index在链表的后半段,那么从后往前找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
}
正文完