LinkedList总结＋数组栈Stack

2019独角兽企业重金招聘Python工程师标准>>>

#LiskedList-> public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

##构造器

• public LinkedList(Collection<? extends E> c)
• public LinkedList() 很熟悉的样子，比ArrayList少了个初始化大小的方法，想想很容易啊，这个是链表，容易扩大小，不是数组！

特点： - 快速失败机制. - Linkedist是由链表实现的，只不过Java中将引用替换成了指针到达了同样的效果，当然，用面向对象来写Node节点比原来大一用面向过程写的那个链表容易很多。 - 从源代码可以看出，LinkedList采用尾查法来插入元素。 - 实现了clone接口何序列化，使用很方便！ - 双向链表查找index位置的节点时，有一个加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。(插入，删除快的原因)

##链栈，链队，链双向队列 ###列子

@Testpublic void test1() {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);//　get,add,remove first都是对队首的操作!/* list.addFirst(4);System.out.println(list);System.out.println(list.getFirst());System.out.println(list.removeFirst());System.out.println(list);*///　get,add,remove last 都是对队尾的操作!/* list.addLast(4);System.out.println(list);System.out.println(list.getLast());System.out.println(list.removeLast());System.out.println(list);*///offer,peek,poll first也是对队首的操作/* System.out.println(list.offerFirst(5));System.out.println(list);System.out.println(list.peekFirst());System.out.println(list.pollFirst());System.out.println(list);*///offer,peek,poll Last也是对队尾的操作/* System.out.println(list.offerLast(5));System.out.println(list);System.out.println(list.peekLast());System.out.println(list.pollLast());System.out.println(list);*///as a stack LIFO/* System.out.println(list.pop());System.out.println(list);list.push(6);System.out.println(list);System.out.println(list.peek());System.out.println(list.pop());System.out.println(list); *///单向队列！！！ FIFO/* list.add(4);//入队　＝＝addLastSystem.out.println(list);System.out.println(list.remove());//出队 ==removeFirstSystem.out.println(list);*///双向队列list.addFirst(4);list.addLast(5);//add=addLastSystem.out.println(list);list.removeFirst();System.out.println(list);list.removeLast();System.out.println(list);list.remove();System.out.println(list);//remove相当于removeFirst}

#Stack

java.lang.Object ↳ java.util.AbstractCollection<E>↳ java.util.AbstractList<E>↳ java.util.Vector<E>↳ java.util.Stack<E>public class Stack<E> extends Vector<E>public class Vector<E>extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable

可以看出Stack的 API很简单，但是继承了Vector（和ArrayList差不多，据说线程安全，在下不相信啊，可以不用Synchronized?），可以看出一下几个特点：

• 具有随机快速访问特点
• 具有clone功能
• 序列化
• 有List和AbstractList已经实现的全部方法。

自己模仿写了个stack，原理差不多。

public class StackDemo {@Testpublic void test() {List<Integer> list = Arrays.asList(1, 2, 3, 4);MyStack<Integer> stack = new MyStack<Integer>(list);//初始大小为５；stack.push(5);stack.push(6);//该扩容了stack.push(7);stack.push(8);//该扩容了System.out.println(stack.peek());//8System.out.println(stack.pop());//8System.out.println(stack.peek());//7}class MyStack<E> {Object[] elems;int size;//数组大小int count;//元素个数int incrementItervel;public MyStack(int size, int incrementItervel) {this.elems = new Object[size];this.size = size;this.incrementItervel = incrementItervel;}public MyStack(int size) {this(size, 2);}public MyStack(Collection<E> collections) {this();addAll(collections);}public MyStack() {this(5);}private void addAll(Collection<E> collections) {Iterator<E> it = collections.iterator();while (it.hasNext()) {ensureCapacity();push(it.next());}}public void ensureCapacity() {while (size <= count) {Object[] objs = new Object[size + incrementItervel];System.arraycopy(elems, 0, objs, 0, elems.length);elems = objs;size += incrementItervel;System.out.println("我扩容了"+size);}}public void push(E e) {ensureCapacity();elems[count++] = e;}public E peek() {return (E) elems[count - 1];}public E pop() {return (E) elems[--count];}} } 我扩容了7 我扩容了9 8 8 7

转载于:https://my.oschina.net/xd03122049/blog/863124

总结

以上是生活随笔为你收集整理的LinkedList总结＋数组栈Stack的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。