文章目录

• 一、什么是LinkedList？
• 二、LinkedList的使用
• 三、LinkedList自实现
• 四、链表实现逆序打印的两种方式（递归和非递归）
• 五、ArrayList和LinkedList有什么区别？

一、什么是LinkedList？

二、LinkedList的使用

构造方法：

public static void main(String[] args) { // 构造一个空的LinkedList List<Integer> list1 = new LinkedList<>();List<String> list2 = new java.util.ArrayList<>(); list2.add("JavaSE");list2.add("JavaWeb"); list2.add("JavaEE"); // 使用ArrayList构造LinkedList List<String> list3 = new LinkedList<>(list2); 
}

 LinkedList的常用方法：

LinkedList的遍历：(foreach遍历、使用迭代器遍历---正向遍历、使用反向迭代器---反向遍历

LinkedList<String> list = new LinkedList<>();list.add("javaSE");list.add("javaWeb");list.add("javaEE");// foreach遍历for (String x: list) {System.out.print(x + " ");}// 使用迭代器遍历---正向遍历ListIterator<String> list1 = list.listIterator();while (list1.hasNext()){System.out.print(list1.next()+" ");}// 使用反向迭代器---反向遍历ListIterator<String> lis2 = list.listIterator(list.size());while (lis2.hasPrevious()){System.out.print(lis2.previous()+" ");}

三、LinkedList自实现

public class MyLinkedList {static class ListNode{int val;ListNode pre;ListNode next;public ListNode(int val){this.val = val;}}public ListNode head;//头部public ListNode tail;//尾部public void addFirst(int data){ListNode node = new ListNode(data);if (head == null){head = node;tail = node;return;}node.next = head;head.pre = node;head = node;}public void addLast(int data){ListNode node = new ListNode(data);if (head == null){head = node;tail = node;return;}tail.next = node;node.pre = tail;tail = node;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data){if (index < 0 || index > size()){System.out.println("index位置不合法！");return false;}if (index == 0){addFirst(data);return true;}if (index == size()){addLast(data);return true;}ListNode indexNode = findNode(index);ListNode node = new ListNode(data);node.pre = indexNode.pre;indexNode.pre.next = node;node.next = indexNode;indexNode.pre = node;return true;}public ListNode findNode(int index){ListNode cur = head;while (index != 0){cur = cur.next;index--;}return cur;}public boolean contains(int key){ListNode cur = head;while (cur != null){if (cur.val == key)return true;cur = cur.next;}return false;}public void remove(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {if (cur == head) {head = head.next;if (head != null) {head.pre = null;} else {tail = null;}} else {cur.pre.next = cur.next;if (cur.next != null) {cur.next.pre = cur.pre;} else {tail = tail.pre;}}return;}cur = cur.next;}}public void removeAllKey(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {if (cur == head) {head = head.next;if (head != null) {head.pre = null;} else {tail = null;}} else {cur.pre.next = cur.next;if (cur.next != null) {cur.next.pre = cur.pre;} else {tail = tail.pre;}}}cur = cur.next;}}public int size(){ListNode cur = head;int count = 0;while (cur != null){count++;cur = cur.next;}return count;}public void display(){ListNode cur = head;while (cur != null){System.out.print(cur.val + " ");cur = cur.next;}}public void clear(){ListNode cur = head;while (cur != null){ListNode temp = cur.next;cur.next = null;cur.pre = null;cur = temp;}head = null;tail = null;}
}

四、链表实现逆序打印的两种方式（递归和非递归）

递归逆序打印：

public void display(ListNode head) {if(head == null) {return;}if(head.next == null) {System.out.print(head.val+" ");return;}display(head.next);System.out.print(head.val+" ");}

非递归逆序打印（用栈实现）：

public void display(ListNode head) {if (head == null) {return;}Stack<ListNode> stack = new Stack<>();ListNode cur = head;while (cur != null) {stack.push(cur);cur = cur.next;}while (!stack.empty()) {ListNode ret = stack.pop();System.out.print(ret.val+" ");}}

五、ArrayList和LinkedList有什么区别？

ArrayList实质是顺序表，底层是一个数组。LinkedList实质是一个链表。

他们都具有增删查改的功能，但是在实现方式上有区别。比如在插入元素的时候，ArrayList往0位置上插入一个元素，就需把整个数组整体往后移动，时间复杂度为O(N)。而LinkedList只需要修改指向就可以了，时间复杂度为O(1)。但是ArrayList可以支持随机访问，时间复杂度为O(1)，所以一般情况下ArrayList顺序表适合频繁根据下标位置访问，LinkedList比较适合插入和删除比较频繁的情况。

从存储上来说，ArrayList顺序表在物理上和逻辑上都是连续的，但是在扩容的时候，可能会造成空间的浪费。而LinkedList在物理上不一定是连续的，在逻辑上是连续的，可以做到随用随取。