【Java数据结构】LinkedList与链表

认识LinkedList

LinkedList就是一个链表，它也是实现List接口的一个类。LinkedList就是通过next引用将所有的结点链接起来，所以不需要数组。LinkedList也是以泛型的方法实现的，所以使用这个类都需要实例化对象。

链表分为很多种，比较常用的就两种：单链表（单向、不带头、非循环）和双链表（双向、不带头、非循环），后面会模拟实现。下面是顺序表和链表的区别：

模拟实现LinkedList

单链表

首先需要创建结点，但是它比顺序表多了一个next引用，可以通过next引用来访问下一个结点，不再需要通过连续地址访问，首先先创建结点这个类，然后再实现增删查改等这些方法：

链表长度、遍历链表、头插法、尾插法、任意位置插入、查找关键字key是否在链表中、删除第一次出现关键字为key的节点、删除所有值为key的节点、清空。

public class MySingle {static class ListNode{private int val;private ListNode next;public ListNode(int val){this.val = val;}}private ListNode head;//头插法public void addFirst(int data){ListNode node = new ListNode(data);node.next = head;head = node;}//尾插法public void addLast(int data){ListNode node = new ListNode(data);if (head == null){head = node;}else {ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}}//任意位置插入public void addIndex(int index,int data){if (index < 0 || index > size()){throw new IndexOutOfException("位置不合法！");}if (index == 0){addFirst(data);return;}ListNode node = new ListNode(data);ListNode cur = head;while (index - 1 != 0){cur = cur.next;index--;}//将index位置前后两个节点和新结点联系起来node.next = cur.next;cur.next = node;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while (cur != null){if (cur.val == key){return true;}}return false;}public ListNode keyPre(int key){ListNode cur = head;while (cur.next != null){if (cur.next.val == key){return cur;}cur = cur.next;}return null;}//删除第一次出现关键字为key的节点public void remove(int key){if (head == null){return;}if (head.val == key){head = head.next;return;}//找到key结点的前一个结点ListNode pre = keyPre(key);ListNode del = pre.next;pre.next = del.next;}//删除所有值为key的节点public void removeAllKey(int key){ListNode pre = head;ListNode cur = head.next;while (cur != null){if (cur.val == key){pre.next = cur.next;cur = cur.next;}else{pre = pre.next;cur = cur.next;}}if (head.val == key){head = head.next;}}//得到单链表的长度public int size(){int count = 0;ListNode cur = head;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;}System.out.println();}
}

双链表（LinkedList）

LinkedList其实就是一个双链表，它既可以访问前驱又可以访问后继，所以可以快速插入和删除。下面是LinkedList模拟实现，比较难的就是插入和删除：

public class MyLinkedList {static class ListNode{private int val;private ListNode prev;private 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;}else {head.prev = node;node.next = head;head = node;}}//尾插法public void addLast(int data){ListNode node = new ListNode(data);if (tail == null){head = node;tail = node;}else{tail.next = node;node.prev = tail;tail = node;//tail = tail.next;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){if (index < 0 || index > size()){throw new IndexOutofBoundException(index+"位置不合理！");}ListNode node = new ListNode(data);ListNode cur = head;while (index > 0){cur = cur.next;index--;}node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while (cur != null){if (cur.val == key){return true;}cur = cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){if (head == null){return ;}ListNode cur = head;while(cur != null ) {if (cur.val == key){if (cur.next == null && cur.prev == null){head = null;tail = null;return;}if (cur.prev == null) {head = cur.next;cur.next.prev = null;return;}if(cur.next == null){tail = cur.prev;cur.prev.next = null;return;}cur.prev.next = cur.next;cur.next.prev = cur.prev;return;}else{cur = cur.next;}}}//删除所有值为key的节点public void removeAllKey(int key){if (head == null){return ;}ListNode cur = head;while(cur != null ) {if (cur.val == key){if (cur.next == null && cur.prev == null){head = null;tail = null;}else if (cur.prev == null) {head = cur.next;cur.next.prev = null;}else if(cur.next == null){tail = cur.prev;cur.prev.next = null;}else {cur.prev.next = cur.next;cur.next.prev = cur.prev;}cur = cur.next;}else{cur = cur.next;}}}//得到单链表的长度public int size(){ListNode cur = head;int size = 0;while (cur != null){size++;cur = cur.next;}return size;}//清空public void clear(){ListNode cur = head;while(cur != null){ListNode curNext = cur.next;cur.prev = null;cur.next = null;cur = curNext;}head = null;tail = null;}//遍历public void display(){ListNode cur = head;while (cur != null){System.out.print(cur.val+"   ");cur = cur.next;}System.out.println();}
}

LinkedList的创建

构造一个对象，可以无参构造（较为常用，在其里初始化一个数组）。

LinkedList的遍历

遍历的方法和ArrayList里一样，三种：for循环、增强for循环、迭代器。这两个遍历方法都是一样的，就不重复叙述。https://blog.csdn.net/2402_84815218/article/details/144038207?spm=1001.2014.3001.5502

LinkedList常用方法

这些方法和ArrayList中的方法差不多都一样，只是实现的过程不一样。这里我就举几个例子：

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(12);//尾插进入list.add(23);System.out.println(list);//【12，23】
//        list.add(3, 100);//插入到第index位置，但是该list中没有第三个位置
//        System.out.println(list);System.out.println(list.get(1));//得到1位置元素  23list.set(1,100);//更新1位置的元素System.out.println(list.get(1));// 100list.remove(1);//删除1位置元素list.clear();//清空链表System.out.println(list);//【】}