概念
LinkedList级双向链表，它的单位是节点，每一个节点都要一个头指针和一个尾指针，称为前驱和后继。第一个节点的头指针指向最后一个节点，最后一个节点的尾指针指向第一个节点，形成环路。
链表增删速度快，查询速度慢。
手写LinkedList
通过今天手写LinkedList，我觉得，我并没有体验到链表比ArrayList快，以后再来深究。
先写一个MyLinkedList类
package _20191210;
import java.util.NoSuchElementException;
public class MyLinkedList<E> {
//List myLikedList = new LinkedList();
Node<E> first;
Node<E> last;
transient int size = 0;
public MyLinkedList(){
}
//linkFirst 插为第一个节点
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<E>(null,e,f);
first = newNode;
if(f == null)
last = newNode;
else
f.prev = newNode;
size++;
// modSize++;
}
//linkLast 插为最后一个节点
private void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<E>(last,e,null);
last = newNode;//将它作为最后一个节点last
if(l == null)//当插入的是列表中的第一个节点时，将该节点设为last与first
first = newNode;
else
l.next = newNode;
size++;
// modCount++;
}
//addFirst 添加到列表的第一个
public void addFirst(E e) {
linkFirst(e);
}
//addLast
public void addLast(E e) {
linkLast(e);
}
//add
public void add(E e) {
linkLast(e);
}
/**
* returns the first element in this List
*/
public E getFirst() {
final Node<E> f = first;
if(f == null) {
throw new NoSuchElementException();
}
return f.item;
}
//getLast返回最后一个元素
public E getLast() {
final Node<E> l = last;
if(last == null) {
throw new NoSuchElementException();
}
return l.item;
}
/**
* removes and returns the first element from the link list.
*/
public E removeFirst(){
final Node<E> f = first;
final Node<E> next = first.next;
if(f == null) {
throw new NoSuchElementException();
}
first = next;
first.prev = null;
size--;
return f.item;
}
/**
* removes and returns the last element from link list
*/
public E removeLast() {
final Node<E> l = last;
if(l == null) {
throw new NoSuchElementException();
}
if(last.prev == null) {
E e = last.item;
last = null;
first = null;
size--;
return e;
}
final Node<E> prev = last.prev;
last = prev;
size--;
return l.item;
}
/**
* returns the size of this list
*/
public int size() {
return size;
}
/**
* remove the first occurrence of the specified element form this list,if it is
* present.
*/
public boolean remove(Object o) {
Node<E> tmp = first;
while(tmp!=null) {
if(tmp.item == o) {
Node<E> prev = tmp.prev;
Node<E> next = tmp.next;
prev.next = next;
next.prev = prev;
size--;
return true;
}
tmp = tmp.next;
}
return false;
}
/**
* returns the index of the first occurrence of the specified element in this list
* or -1 if this list does not contain the element
*/
public int indexOf(Object o) {
int index = 0;
if(null == o) {
for(Node<E> f = first;f != null;f = f.next) {
if(f.item==o) {
return index;
}
index++;
}
}else {
for(Node<E> f = first;f != null;f = f.next) {
if(o.equals(f.item)) {
return index;
}
index++;
}
}
return -1;
}
//toString
public String toString() {
StringBuffer sb = new StringBuffer();
sb.append("[");
Node<E> tmp = null;
tmp = first;
do{
if(tmp==null) break;
sb.append(tmp.item);
if(tmp.next!=null) sb.append(", ");
tmp = tmp.next;
}while(tmp!=null);
sb.append("]");
return sb.toString();
}
//内部类：节点
private static class Node<E>{
E item;//本体
Node<E> next;//后继
Node<E> prev;//前驱
public Node(Node<E> prev,E element,Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
再写一个MyLinkedListTest测试类，测试手写LinkedList与官方LinkedList的运行结果。
package _20191210;
import java.util.LinkedList;
import java.util.List;
public class MyLinkedListTest {
public static void main(String[] args) {
System.out.println("---------自己写的LinkedList-----------");
MyLinkedList<String> mk = new MyLinkedList<>();
mk.add("Y");
mk.add("E");
mk.add("S");
System.out.println(mk);
System.out.println(mk.size());
System.out.println("移除E:"+mk.remove("E"));
System.out.println(mk);
System.out.println(mk.getFirst());
System.out.println(mk.getLast());
System.out.println("S的位置为："+mk.indexOf("S"));
System.out.println("removeFirst:"+mk.removeFirst());
System.out.println(mk.size());
System.out.println(mk);
System.out.println("removeLast:"+mk.removeLast());
System.out.println(mk);
System.out.println("---------官方LinkedList-------------");
LinkedList<String> linkList = new LinkedList<>();
linkList.add("Y");
linkList.add("E");
linkList.add("S");
System.out.println(linkList);
System.out.println(linkList.size());
System.out.println("移除E:"+linkList.remove("E"));
System.out.println(linkList);
System.out.println(linkList.getFirst());
System.out.println(linkList.getLast());
System.out.println("S的位置为："+linkList.indexOf("S"));
System.out.println("removeFirst:"+linkList.removeFirst());
System.out.println(linkList.size());
System.out.println(linkList);
System.out.println("removeLast:"+linkList.removeLast());
System.out.println(linkList);
}
}