链表
链表的数据存储在 “节点” 中，链表就像火车一样，每一节都有一个引用来指向下一节，也就是每一个 “节点” 会指向它的下一个 “节点” 。
链表是真正的、最简单的动态数据结构，不需要像数组那样处理固定容量的问题(扩缩容处理)，缺点是丧失了随机访问的能力。
链表代码
public class LinkedList<E> {
// 虚拟头节点
private Node dummyHead;
private int size;
public LinkedList() {
dummyHead = new Node(null, null);
}
/**
* 向链表的 index 索引位置添加新的元素，时间复杂度O(n)
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add Failed.Illegal index.");
}
// 默认第一个节点为虚拟头节点
Node prevNode = dummyHead;
// 遍历 index -1 次，找到 index 的前一个节点
for (int i = 0; i < index; i++) {
prevNode = prevNode.next;
}
// 将前一个节点的下一个节点指向新建的节点
// 新建节点的下一个节点指向前一个节点的下一个节点
prevNode.next = new Node(e, prevNode.next);
size++;
}
/**
* 在链表头添加新的元素，时间复杂度O(1)
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 在链表尾添加新的元素，时间复杂度O(n)
*/
public void addLast(E e) {
add(size, e);
}
/**
* 删除指定 index 索引位置的节点，时间复杂度O(n)
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove Failed.Illegal index.");
}
Node prevNode = dummyHead;
// 找到前一个节点
for (int i = 0; i < index; i++) {
prevNode = prevNode.next;
}
// 要删除的节点
Node delNode = prevNode.next;
prevNode.next = delNode.next;
// 将要删除的节点的下一个节点指向 null ,利于GC释放内存
delNode.next = null;
size--;
return delNode.e;
}
/**
* 删除元素
*/
public void removeElement(E e) {
dummyHead.next = removeElement(dummyHead.next, e);
}
/**
* 向以 node 为根节点的链表中删除元素为e的节点
* 返回删除元素后的根节点
*/
private Node removeElement(Node node, E e) {
if (node == null) {
return node;
}
if (node.e.equals(e)) {
size--;
return node.next;
} else {
node.next = removeElement(node.next, e);
}
return node;
}
/**
* 删除元素非递归方式
*/
public void removeElementNR(E e) {
Node prevNode = dummyHead;
for (int i = 0; i < size; i++) {
Node curNode = prevNode.next;
if (curNode.e.equals(e)) {
prevNode.next = curNode.next;
curNode.next = null;
size--;
break;
} else {
prevNode = prevNode.next;
}
}
}
/**
* 删除链表头的节点，时间复杂度O(1)
*/
public E removeFirst() {
return remove(0);
}
/**
* 删除链表尾的节点，时间复杂度O(n)
*/
public E removeLast() {
return remove(size - 1);
}
/**
* 更新 index 索引为新的元素，时间复杂度O(n)
*/
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set Failed.Illegal index.");
}
Node curNode = dummyHead.next;
for (int i = 0; i < index; i++) {
curNode = curNode.next;
}
curNode.e = e;
}
/**
* 获取链表的 index 索引位置的元素，时间复杂度O(n)
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get Failed.Illegal index.");
}
Node curNode = dummyHead.next;
for (int i = 0; i < index; i++) {
curNode = curNode.next;
}
return curNode.e;
}
/**
* 获取链表头的元素
*/
public E getFirst() {
return get(0);
}
/**
* 获取链表尾的元素
*/
public E getLast() {
return get(size - 1);
}
/**
* 查找链表中是否存在元素e，时间复杂度O(n)
*/
public boolean contains(E e) {
Node curNode = dummyHead.next;
while (curNode != null) {
if (curNode.e.equals(e)) {
return true;
} else {
curNode = curNode.next;
}
}
return false;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("LinkedList: ");
// 这种写法是可以的
/* Node curNode = dummyHead.next;
while (curNode != null) {
res.append(curNode + "->");
curNode = curNode.next;
}*/
for (Node node = dummyHead.next; node != null; node = node.next) {
res.append(node + "->");
}
res.append("NULL");
return res.toString();
}
/**
* @Description: 节点类
* @Author: fanda
* @Date: 2019/5/13
*/
private class Node {
public E e;
public Node next;
public Node() {
}
public Node(E e) {
this.e = e;
}
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
@Override
public String toString() {
return e.toString();
}
}
}
时间复杂度分析
添加操作
addLast(e) ，O(n) ，跟链表里面的元素个数 n 有关。
addFirst(e) ，O(1) ，跟链表里面的元素个数 n 无关。
add(index ,e) ，O(2/n) = O(n) ，跟链表里面的元素个数 n 有关，可以想像成链表里面的元素需要移动 2/n 次，常数忽略。
因此，添加操作的时间复杂度为 O(n) 级别的，取最糟糕的情况。
删除操作
removeLast(e) ，O(n) ，跟链表里面的元素个数 n 有关。
removeFirst(e) ，O(1) ，跟链表里面的元素个数 n 无关。
remove(index ,e) ，O(2/n) = O(n) ，跟链表里面的元素个数 n 有关，可以想像成链表里面的元素需要移动 2/n 次，常数忽略。
因此，删除操作的时间复杂度为 O(n) 级别的，取最糟糕的情况。
修改操作
set(index ,e) ，O(n) ，跟链表里面的元素个数 n 有关，(即不支持随机访问)
查询操作
get(index) ，O(n) ，跟链表里面的元素个数 n 有关。
contain(e) ，O(n) ，跟链表里面的元素个数 n 有关。
总结：链表的增删改查操作的时间复杂度全为 O(n) 级别的，但是如果只对链表头做操作的话，复杂度是 O(1) 级别的，因此，链表只适合对链表头数据进行操作,由于没有动态数组的扩缩容操作，此时性能会更好一些。
底层为链表的栈
public class LinkedListStack<E> implements Stack<E> {
private LinkedList<E> linkedList;
public LinkedListStack() {
linkedList = new LinkedList<>();
}
@Override
public int getSize() {
return linkedList.getSize();
}
@Override
public boolean isEmpty() {
return linkedList.isEmpty();
}
@Override
public void push(E e) {
linkedList.addFirst(e);
}
@Override
public E pop() {
return linkedList.removeFirst();
}
@Override
public E peek() {
return linkedList.getFirst();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("LinkedListStack: TOP ");
res.append(linkedList);
return res.toString();
}
}
ArrayStack 和 LinkedListStack 的性能比较
public class Main {
public static void main(String[] args) {
int opCount = 100000;
ArrayStack<Integer> arrayStack = new ArrayStack<>();
LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
System.out.println("arrayStack need time = " + testStack(arrayStack, opCount));
System.out.println("linkedListStack need time = " + testStack(linkedListStack, opCount));
}
/**
* 测试栈的运行时间
*/
private static double testStack(Stack<Integer> stack, int opCount) {
long startTime = System.nanoTime();
Random random = new Random();
for (int i = 0; i < opCount; i++) {
stack.push(random.nextInt(Integer.MAX_VALUE));
}
for (int i = 0; i < opCount; i++) {
stack.pop();
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
}
运行结果：
arrayStack need time = 0.064225789
linkedListStack need time = 0.019631385
总结：LinkedListStack 和 ArrayStack 都是 O(1) 级别的，性能相差不大，如果需要 new 的数据量较大的话，LinkedListStack 的性能可能比 ArrayStack 还差。
底层为链表的队列
public class LinkedListQueue<E> implements Queue<E> {
//头节点和尾节点
private Node head, tail;
private int size;
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void enqueue(E e) {
// 如果链表为空，因为有元素的时 tail 不为 null
if (tail == null) {
tail = new Node(e);
// 此时都指向同一个节点
head = tail;
} else {
// 直接将最后的节点指向新的节点即可
tail.next = new Node(e);
// 维护一下 tail 的位置，保证 tail 指向最后的节点
tail = tail.next;
}
// 维护一下数量
size++;
}
@Override
public E dequeue() {
if (isEmpty()) {
throw new IllegalArgumentException("Queue is empty.");
}
Node retNode = head;
// 将当前的头节点指向下一个节点
head = head.next;
// 将要删除的节点的下一个节点指向 null ,利于GC释放内存
retNode.next = null;
// 如果链表为空，需要将 tail 置空
if (head == null) {
tail = null;
}
// 维护一下数量
size--;
return retNode.e;
}
@Override
public E getFront() {
if (isEmpty()) {
throw new IllegalArgumentException("Queue is empty.");
}
return head.e;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue: front ");
Node curNode = head;
while (curNode != null) {
res.append(curNode + "->");
curNode = curNode.next;
}
res.append("NULL tail");
return res.toString();
}
/**
* @Description: 节点类
* @Author: fanda
* @Date: 2019/5/13
*/
private class Node {
public E e;
public Node next;
public Node() {
}
public Node(E e) {
this.e = e;
}
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
@Override
public String toString() {
return e.toString();
}
}
}
LinkedListQueue 、LoopQueue 、ArrayQueue 性能比较
public class QueueMain {
public static void main(String[] args) {
int opCount = 10000;
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
LoopQueue<Integer> loopQueue = new LoopQueue<>();
LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
System.out.println("arrayQueue need time = " + testQueue(arrayQueue, opCount));
System.out.println("loopQueue need time = " + testQueue(loopQueue, opCount));
System.out.println("linkedListQueue need time = " + testQueue(linkedListQueue, opCount));
}
/**
* 测试队列的运行时间
*/
private static double testQueue(Queue<Integer> queue, int opCount) {
long startTime = System.nanoTime();
Random random = new Random();
for (int i = 0; i < opCount; i++) {
queue.enqueue(random.nextInt(Integer.MAX_VALUE));
}
for (int i = 0; i < opCount; i++) {
queue.dequeue();
}
long endTime = System.nanoTime();
// 纳秒转成秒
return (endTime - startTime) / 1000000000.0;
}
}
测试数据量为 10000 时的运行结果：
arrayQueue need time = 0.412026981
loopQueue need time = 0.005801394
linkedListQueue need time = 0.003621125
测试数据量为 100000 时的运行结果：
arrayQueue need time = 62.304321669
loopQueue need time = 0.044549178
linkedListQueue need time = 0.061632932
总结： 因为 LinkedListQueue 和 LoopQueue 的复杂度都是 O(1) ，所以性能相差不大，但是 ArrayQueue 的复杂度为 O(n)的，所以性能最差。当数据量较大的时候，LinkedListQueue 所消耗的时间比 LoopQueue 还要大。
递归
本质上，是将原来的问题，转化为更小的同一个问题。
比如，数组求和：
Sum(arr[0…n-1]) = arr[0] + Sum(arr[1…n-1])
Sum(arr[1…n-1]) = arr[1] + Sum(arr[2…n-1])
…….
Sum(arr[n-1…n-1]) = arr[n-1] + Sum([])
分析：求数组索引从 0 到 n-1 的和，就是求索引为 0 的值加上索引从 1 到 n-1 的和，依此类推，这样就变成更小的同一问题了。
求和代码如下：
public class Sum {
public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.out.println("sum() = " + sum(arr));
}
/**
* 对数组 arr 进行求和
*/
public static int sum(int[] arr) {
if (arr == null) {
return 0;
}
return sum(arr, 0);
}
/**
* 计算 arr[index...n]这个区间内所有数字的和
*/
private static int sum(int[] arr, int index) {
// 递归到底的情况，即最基本的问题
if (index == arr.length) {
return 0;
}
// 把原问题转化成更小的问题
return arr[index] + sum(arr, index + 1);
}
}
LeetCode 的题目解答
203.移除链表元素
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
解题代码如下：
public class Soluction203 {
public static void main(String[] args) {
int[] arr = new int[]{3, 53, 2, 7, 12, 5, 3};
System.out.println(removeElements3(new ListNode(arr), 3));
}
/**
* 删除链表中等于给定值 val 的所有节点，不带虚拟头节点方式
*/
public ListNode removeElements(ListNode head, int val) {
// 如果删除的正好是头节点，这里用 while 语句，因为下个节点也可能要删除掉
while (head != null && head.val == val) {
ListNode delNode = head;
head = head.next;
delNode.next = null;
}
// 链表为空了，直接返回 null
if (head == null) {
return null;
}
// 删除的值在中间位置时
ListNode prevNode = head;
while (prevNode.next != null) {
if (prevNode.next.val == val) {
ListNode delNode = prevNode.next;
prevNode.next = delNode.next;
delNode.next = null;
} else {
prevNode = prevNode.next;
}
}
return head;
}
/**
* 删除链表中等于给定值 val 的所有节点，带虚拟头节点方式
*/
public static ListNode removeElements2(ListNode head, int val) {
ListNode dummyHead = new ListNode(-1, head);
ListNode prevNode = dummyHead;
while (prevNode.next != null) {
if (prevNode.next.val == val) {
// 如果 prevNode.next 是要删除的值，则跳过，直接指向它的下一个节点
prevNode.next = prevNode.next.next;
} else {
prevNode = prevNode.next;
}
}
// 返回真正的头结点
return dummyHead.next;
}
/**
* 删除链表中等于给定值 val 的所有节点，递归方式
*/
public static ListNode removeElements3(ListNode node, int val) {
// 递归到底的情况，即最基本的问题
if (node == null) {
return null;
}
// 把原问题转化成更小的问题
node.next = removeElements3(node.next, val);
return node.val == val ? node.next : node;
}
}