数据结构之链表（LinkedList详解）

 

文章目录

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

---

一、什么是LinkedList？

二、LinkedList的使用

构造方法：

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

 LinkedList的常用方法：

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

LinkedList list = new LinkedList<>();
        list.add("javaSE");
        list.add("javaWeb");
        list.add("javaEE");
        // foreach遍历
        for (String x: list) {
            System.out.print(x + " ");
        }
        // 使用迭代器遍历---正向遍历
        ListIterator list1 = list.listIterator();
        while (list1.hasNext()){
            System.out.print(list1.next()+" ");
        }
        // 使用反向迭代器---反向遍历
        ListIterator 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 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在物理上不一定是连续的，在逻辑上是连续的，可以做到随用随取。