vlambda博客
学习文章列表

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ transient int size = 0; transient Node<E> first; transient Node<E> last;  public LinkedList() { }  public LinkedList(Collection<? extends E> c) { this(); addAll(c); }  public boolean addAll(Collection<? extends E> c) { return addAll(size, c); }  public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index);  Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false;  Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; }  for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; }  if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; }  size += numNew; modCount++; return true; }  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; } }  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; } }  }

linkedList.add(E e)linkedList.add(int index, E element)linkedList.addAll(Collection<? extends E> c)

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)); }  void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } public boolean addAll(Collection<? extends E> c) { return addAll(size, c); }

linkedList.remove(int index)linkedList.remove(Object o)linkedList.remove(Collection<?> c)

public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } 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; size--; modCount++; return element; } 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; }  public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); boolean modified = false; Iterator<?> it = iterator(); while (it.hasNext()) { if (c.contains(it.next())) { it.remove(); modified = true; } } return modified; }

public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; }

public E get(int index) { checkElementIndex(index);//判断是否越界 [0,size) return node(index).item; //调用node()方法 取出 Node节点，}   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; }  public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }

public Iterator<E> iterator() { return listIterator(); } public ListIterator<E> listIterator() { return listIterator(0); } public ListIterator<E> listIterator(final int index) { rangeCheckForAdd(index);  return new ListItr(index); } private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) { cursor = index; }  public boolean hasPrevious() { return cursor != 0; }  public E previous() { checkForComodification(); try { int i = cursor - 1; E previous = get(i); lastRet = cursor = i; return previous; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } }  public int nextIndex() { return cursor; }  public int previousIndex() { return cursor-1; }  public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification();  try { AbstractList.this.set(lastRet, e); expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }  public void add(E e) { checkForComodification();  try { int i = cursor; AbstractList.this.add(i, e); lastRet = -1; cursor = i + 1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }

public interface Deque<E> extends Queue<E> { void addFirst(E e);//插入头部，异常会报错 boolean offerFirst(E e);//插入头部，异常不报错 E getFirst();//获取头部，异常会报错 E peekFirst();//获取头部，异常不报错 E removeFirst();//移除头部，异常会报错 E pollFirst();//移除头部，异常不报错  void addLast(E e);//插入尾部，异常会报错 boolean offerLast(E e);//插入尾部，异常不报错 E getLast();//获取尾部，异常会报错 E peekLast();//获取尾部，异常不报错 E removeLast();//移除尾部，异常会报错 E pollLast();//移除尾部，异常不报错}

public interface Queue<E> extends Collection<E> { //往队列插入元素，如果出现异常会抛出异常 boolean add(E e); //往队列插入元素，如果出现异常则返回false boolean offer(E e); //移除队列元素，如果出现异常会抛出异常 E remove(); //移除队列元素，如果出现异常则返回null E poll(); //获取队列头部元素，如果出现异常会抛出异常 E element(); //获取队列头部元素，如果出现异常则返回null E peek();}

package com.ysten.leakcanarytest; import java.util.Collection;import java.util.LinkedList; /** * desc : 实现栈 * time : 2018/10/31 0031 19:07 * * @author : wangjitao */public class Stack<T>{ private LinkedList<T> stack;  //无参构造函数 public Stack(){ stack=new LinkedList<T>(); } //构造一个包含指定collection中所有元素的栈 public Stack(Collection<? extends T> c){ stack=new LinkedList<T>(c); } //入栈 public void push(T t){ stack.addFirst(t); } //出栈 public T pull(){ return stack.remove(); } //栈是否为空 boolean isEmpty(){ return stack.isEmpty(); }  //打印栈元素 public void show(){ for(Object o:stack) System.out.println(o); }}

public static void main(String[] args){ Stack<String> stringStack = new Stack<>(); stringStack.push("1"); stringStack.push("2"); stringStack.push("3"); stringStack.push("4"); stringStack. show(); }

public interface RandomAccess {}

int binarySearch(List<? extends Comparable<? super T>> list, T key) { if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); }

int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) { int low = 0; int high = list.size()-1;  while (low <= high) { int mid = (low + high) >>> 1; Comparable<? super T> midVal = list.get(mid); int cmp = midVal.compareTo(key);  if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found }   int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key){ int low = 0; int high = list.size()-1; ListIterator<? extends Comparable<? super T>> i = list.listIterator();  while (low <= high) { int mid = (low + high) >>> 1; Comparable<? super T> midVal = get(i, mid); int cmp = midVal.compareTo(key);  if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found }

LinkedList linkedList = new LinkedList();for(int i = 0; i < 100000; i++){ linkedList.add(i);}// 迭代器遍历 long start = System.currentTimeMillis(); Iterator iterator = linkedList.iterator(); while(iterator.hasNext()){ iterator.next(); } long end = System.currentTimeMillis(); System.out.println("Iterator："+ (end - start) +"ms");

// 顺序遍历(随机遍历) long start = System.currentTimeMillis(); for(int i = 0; i < linkedList.size(); i++){ linkedList.get(i);}long end = System.currentTimeMillis();System.out.println("for ："+ (end - start) +"ms");

long start = System.currentTimeMillis();for(Object i : linkedList);long end = System.currentTimeMillis();System.out.println("增强for ："+ (end - start) +"ms");

long start = System.currentTimeMillis();while(linkedList.size() != 0){ linkedList.removeFirst();}long end = System.currentTimeMillis();System.out.println("removeFirst ："+ (end - start) +"ms");

long start = System.currentTimeMillis();for (int i = 0; i < arrayList.size(); i++) { arrayList.get(i);} long end = System.currentTimeMillis(); System.out.println("for ："+ (end - start) +"ms");

long start = System.currentTimeMillis();Iterator iterable = arrayList.iterator() ;while (iterable.hasNext()){ iterable.next();} long end = System.currentTimeMillis(); System.out.println("for ："+ (end - start) +"ms");