LinkedList也就是我们在数据结构中链表，这种数据结构具有这样的特性:
分配内存空间不是必须连续的。
插入删除很快，只要修改前后指针就可以了 ，时间复杂度为O(1)。
访问比较慢，必须从第一个元素开始遍历，时间复杂度为O(n)。
在Java中，LinkedList提供了极其丰富的方法，可以模拟链式队列，链式堆栈等数据结构，给我们带来了极大的方便。下面来康康用法。
add(增加一个元素)
boolean add(E e)在链表后添加一个元素，如果成功返回ture，如果不成功，则返回false。
void addFirst(E e)在链表头部添加一个元素。
void addLast(E e)在链表尾部添加一个元素。
void add(int index ，E element)在指定位置添加一个元素。
代码演示：
public class LinkedListMethodsDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");
System.out.println(linkedList);
linkedList.addFirst("addFirst");
System.out.println(linkedList);
linkedList.addLast("addLast");
System.out.println(linkedList);
linkedList.add(2, "addByIndex");
System.out.println(linkedList);
}
}
结果：
[first, second, third]
[addFirst, first, second, third]
[addFirst, first, second, third, addLast]
[addFirst, first, addByIndex, second, third, addLast]
remove(移出)：
E remove() 删除链表中第一个元素。
boolean remove(Object o)移除链表中指定的元素。
E remove(int index)：移除链表中指定位置的元素。
E removeFirst() 移除链表中的第一个元素，与remove类似。
E removeLast()移出链表中的最后一个元素。
boolean removeFirstOccurrence(Object o)移除链表中第一次元素出现所在的位置。
boolean removeLastOccurrence(Object o)移除链表中最后一次元素出现所在的位置。
代码演示
public class LinkedListMethodsDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("first");
linkedList.add("second");
linkedList.add("second");
linkedList.add("third");
linkedList.add("four");
linkedList.add("five");
System.out.println(linkedList);
linkedList.remove();
System.out.println("remove: " + linkedList);
linkedList.remove("second");
System.out.println("remove(Object): " + linkedList);
linkedList.remove("six");
System.out.println("remove(Object) not exist: " + linkedList);
linkedList.remove(2);
System.out.println("remove(index): " + linkedList);
linkedList.removeFirst();
System.out.println("removeFirst: " + linkedList);
linkedList.removeLast();
System.out.println("removeLast:" + linkedList);
System.out.println("----------------------------------");
linkedList.clear();
linkedList.add("first");
linkedList.add("second");
linkedList.add("first");
linkedList.add("third");
linkedList.add("first");
linkedList.add("five");
System.out.println(linkedList);
linkedList.removeFirstOccurrence("first");
System.out.println("removeFirstOccurrence: " + linkedList);
linkedList.removeLastOccurrence("first");
System.out.println("removeLastOccurrence: " + linkedList);
}
}
结果：
[first, second, second, third, four, five]
remove: [second, second, third, four, five]
remove(Object): [second, third, four, five]
remove(Object) not exist: [second, third, four, five]
remove(index): [second, third, five]
removeFirst: [third, five]
removeLast:[third]
----------------------------------
[first, second, first, third, first, five]
removeFirstOccurrence: [second, first, third, first, five]
removeLastOccurrence: [second, first, third, five]
get(获取)
E get(int index) 按照下边获取元素
E getFirst()：获取第一个元素
E getLast()：获取最后一个元素。
代码演示
public class LinkedListMethodsDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("first");
linkedList.add("second");
linkedList.add("second");
linkedList.add("third");
linkedList.add("four");
linkedList.add("five");
System.out.println(linkedList);
linkedList.get(3);
System.out.println("get(index): " + linkedList.get(3));
linkedList.getFirst();
System.out.println("getFirst: " + linkedList.getFirst());
linkedList.getLast();
System.out.println("getLast: " + linkedList.getLast());
System.out.println(linkedList);
}
}
结果：
[first, second, second, third, four, five]
get(index): third
getFirst: first
getLast: five
[first, second, second, third, four, five]
push，pop，poll
void push(E e) ，与addFirst一样，实际上他就是addFirst,在链表头部添加一个元素。
E pop()：与removeFirst一样，实际上就是removeFirst。移除链表中的第一个元素.
E poll()：查询并移除第一个元素;
代码演示：
public class LinkedListMethodsDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.push("first");
linkedList.push("second");
linkedList.push("second");
linkedList.push("third");
linkedList.push("four");
linkedList.push("five");
System.out.println("linkedList: " + linkedList);
System.out.println("pop: " + linkedList.pop());
System.out.println("after pop: " + linkedList);
System.out.println("poll: " + linkedList.poll());
System.out.println("after poll: " + linkedList);
}
}
结果：
linkedList: [five, four, third, second, second, first]
pop: five
after pop: [four, third, second, second, first]
poll: four
after poll: [third, second, second, first]
通过代码示例可以看出：push，pop的操作已经很接近stack(栈)的操作了。
如果链表为空的时候，看看poll与pop是啥区别：
public class LinkedListMethodsDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
System.out.println("poll: " + linkedList.poll());
System.out.println("pop: " + linkedList.pop());
}
}
结果：
poll: null
Exception in thread "main" java.util.NoSuchElementException
at java.util.LinkedList.removeFirst(LinkedList.java:270)
at java.util.LinkedList.pop(LinkedList.java:801)
at org.ks.algorithm.LinkedListMethodsDemo.main(LinkedListMethodsDemo.java:13)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:483)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:144)
可以看出poll返回null，而pop则产生异常。
peek
E peek() : 获取第一个元素但是不移除。
E peekFirst ： 获取第一个元素但是不移除。
E peekLast : 获取最后一个元素但是不移除。
代码演示：
public class LinkedListMethodsDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.push("first");
linkedList.push("second");
linkedList.push("second");
linkedList.push("third");
linkedList.push("four");
linkedList.push("five");
System.out.println("linkedList: " + linkedList);
System.out.println("peek: " + linkedList.peek());
System.out.println("peekFirst: " + linkedList.peekFirst());
System.out.println("peekLast: " + linkedList.peekLast());
System.out.println("linkedList: " + linkedList);
}
}
输出：
linkedList: [five, four, third, second, second, first]
peek: five
peekFirst: five
peekLast: first
linkedList: [five, four, third, second, second, first]
如果没找到对应的元素，统统输出null：
public class LinkedListMethodsDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
System.out.println("linkedList: " + linkedList);
System.out.println("peek: " + linkedList.peek());
System.out.println("peekFirst: " + linkedList.peekFirst());
System.out.println("peekLast: " + linkedList.peekLast());
}
}
输出：
linkedList: []
peek: null
peekFirst: null
peekLast: null
offer
boolean offer(E e) : 在链表尾部插入一个元素。
boolean offerFirst(E e) : 与addFirst一样，实际上它就是addFirst；
boolean offerLast(E e) : 与addLast一样，实际上它就是addLast；
代码演示：
public class LinkedListMethodsDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.push("first");
linkedList.push("second");
linkedList.push("second");
linkedList.push("third");
linkedList.push("four");
linkedList.push("five");
System.out.println("linkedList: " + linkedList);
linkedList.offer("six");
System.out.println("linkedList: " + linkedList);
linkedList.offerFirst("zero");
System.out.println("linkedList: " + linkedList);
linkedList.offerLast("seven");
System.out.println("linkedList: " + linkedList);
}
}
输出：
linkedList: [five, four, third, second, second, first]
linkedList: [five, four, third, second, second, first, six]
linkedList: [zero, five, four, third, second, second, first, six]
linkedList: [zero, five, four, third, second, second, first, six, seven]
LinkedList中常用的方法基本都列出来了，当然还有一些其他的例子，这里就一起演示了：
boolean contains(Object o) : 如果此列表包含指定元素，则返回 true。
E element() :获取但不移除此列表的头（第一个元素）。
E set(int index ,E element) : 将此列表中指定位置的元素替换为指定的元素。
List<E> subList(int fromIndex,int toIndex) :返回列表中指定的 fromIndex（包括 ）和 toIndex（不包括）之间的部分视图。（如果 fromIndex 和 toIndex 相等，则返回的列表为空）。
public class LinkedListMethodsDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.push("first");
linkedList.push("second");
linkedList.push("second");
linkedList.push("third");
linkedList.push("four");
linkedList.push("five");
System.out.println("linkedList: " + linkedList);
System.out.println("linkedList.contains(\"second\"): " + linkedList.contains("second"));
System.out.println("linkedList.contains(\"six\"): " + linkedList.contains("six"));
System.out.println("linkedList.element(): " + linkedList.element());
System.out.println("linkedList: " + linkedList);
System.out.println("linkedList.set(3, \"set\"): " + linkedList.set(3, "set"));
System.out.println("linkedList: " + linkedList);
System.out.println("linkedList.subList(2,4): " + linkedList.subList(2,4));
System.out.println("linkedList: " + linkedList);
}
}
输出：
linkedList: [five, four, third, second, second, first]
linkedList.contains("second"): true
linkedList.contains("six"): false
linkedList.element(): five
linkedList: [five, four, third, second, second, first]
linkedList.set(3, "set"): second
linkedList: [five, four, third, set, second, first]
linkedList.subList(2,4): [third, set]
linkedList: [five, four, third, set, second, first]
