linkedlist
LinkedList 常用方法：
增加：addFirst(E e),addLast(E e),offer(E e),offerFirst(E e),offerLast(E e)
删除：poll(),pollFirst(),pollLast(),removeFirst(),removeLast()
修改：set(int index, E element)
查看：element()，getFirst(),getLast(),indexOf(Object o),lastIndexOf(Object o),peek(),peekFirst(),peekLast()
判断：
示例代码：
// 现有一个linkedlist集合对象 public static void main(String[] args) { LinkedList<String> list = new LinkedList(); // 能否重复添加数据 list.add("aaaa"); list.add("bbbb"); list.add("aaaa"); list.add("cccc"); System.out.println(list); // 收尾添加 list.addFirst("ffff"); list.addLast("zzzz"); System.out.println(list); // 添加元素到尾端 list.offer("ll"); System.out.println(list); list.offerFirst("pp"); list.offerLast("rr"); // 删除首个元素 System.out.println(list); System.out.println("删除"+list.poll());//删除头上的元素，并且返回删除的元素 System.out.println("删除"+list.pollFirst()); System.out.println("删除"+list.pollLast()); System.out.println(list); //查找头尾元素 System.out.println(list.peek()); System.out.println(list.peekLast()); // list.clear(); // 方法的举例 System.out.println(list); System.out.println(list.pollLast());//如果没有返回null，不影响程序执行 System.out.println(list.removeFirst());//Exception in thread "main" java.util.NoSuchElementException，会报错， // 遍历 System.out.println("----------"); // 1 for (int i=0; i<list.size();i++){ System.out.println(list.get(i)); } // 2 for (String s : list) { System.out.println(s); } // 3 Iterator it = list.iterator(); while (it.hasNext()){ System.out.println(it.next()); } // 可能源码看到,这个迭代器相对好，内存上的节省 for ( Iterator it1 = list.iterator();it1.hasNext();){ System.out.println(it1.next()); }
为什么有功能相同的方法：以
pollFirst(),pollLast(),
removeFirst(),removeLast()
为例：
removeFirst是早版本的
pollFirst是jdk1.6版本的
实测区别：
// 方法的举例 System.out.println(list); System.out.println(list.pollLast());//如果没有返回null，不影响程序执行 System.out.println(list.removeFirst());//Exception in thread "main" java.util.NoSuchElementException，会报错，
同样是空的集合，pollFirst删除第一个如果没有返回null，无报错，removeFirst会报错没有数据
相比之下1.6之后的方法提高了健壮性，其他类似方法与这一对一致,
遍历方式：
源码看到,这个迭代器相对好，内存上的节省，例子：
for ( Iterator it1 = list.iterator();it1.hasNext();){ System.out.println(it1.next()); }
linkedlist的原理
对比学习：
Linkedlist是双向链表：
简要底层原理图：
模拟一个linkedList
首先是我们的节点类
package linkedListPrc; import javax.xml.soap.Node; public class Test02 {//节点类 // 三个属性 // 上一个元素的地址 private Test02 pre; // 当前存放的元素 private Object obj; // 下一个元素的地址 private Test02 next; public Test02 getPre() { return pre; } public void setPre(Test02 pre) { this.pre = pre; } public Object getObj() { return obj; } public void setObj(Object obj) { this.obj = obj; } public Test02 getNext() { return next; } public void setNext(Test02 next) { this.next = next; } public Test02() { } }
之后就是我们的mylist源码
public class MyLinkedList { // 链中一个定有一个首节点 Test02 first; // 链中一个有一个尾节点 Test02 last; // 计数器 int count =0; // 提供一个构造器 public MyLinkedList(){ } // 元素添加方法 public void add(Object o){ if (first ==null){//证明添加的元素是第一个 // 那接下来我们需要吧添加的元素封装成一个node Test02 n = new Test02(); n.setPre(null); n.setObj(o); n.setNext(null); first = n; last = n; }else {//证明以及不是链中的第一个节点了 // 先把添加的元素封装成一个node对象 Test02 n = new Test02(); n.setPre(last); n.setObj(o); // 当前链中的最后一个节点的下一个元素要指向n last.setNext(n); // 将最后一个节点变成n last = n; } count++; } public int getSize(){ return count; } // 通过下标得到元素 public Object getelByindex(int index){ if (index>count){ System.out.println("这个索引上没有数据，检查插入的元素是否达到查找索引的数量"); } // 获取链表的头元素 Test02 n = first; for (int i = 0;i< index;i++){ // 一路next找到想要的元素 n = n.getNext(); } return n.getObj(); } }
linkdelist部分源码解读
public class LinkedList<E>{ //长度 transient int size = 0; //首位 transient Node<E> first; //尾位 transient Node<E> last; //封装节点对象方法 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 addAll(Collection<? extends E> c) { return addAll(size, c); } void linkLast(E e) { //添加的元素e final Node<E> l = last; //将链表中的last节点给l，如果是第一个元素的话l为null final Node<E> newNode = new Node<>(l, e, null); //将元素封装为一个node的具体对象 last = newNode; //将链表的为节点指向新创建的对象 if (l == null)如果添加的是第一个节点 first = newNode;//将链表的first节点只想为新节点 else //如果添加的不是第一个节点 l.next = newNode;//将l的下一个指向新的节点 size++; //集合中元素数量加1 modCount++; } //查找方法 public E get(int index) { checkElementIndex(index); return node(index).item; } //二分查找的方式遍历链表 Node<E> node(int 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; } } }
