Java数据结构和算法(四)--链表

淡淡的烟草味﹌ 2021-11-05 12:42 308阅读 0赞

日常开发中，数组和集合使用的很多，而数组的无序插入和删除效率都是偏低的，这点在学习ArrayList源码的时候就知道了，因为需要把要

插入索引后面的所以元素全部后移一位。

而本文会详细讲解链表，可以解决数组的部分问题，相比数组的大小不可更改，链表更加灵活，在学习LinkedList源码对链表有了一个大致的

了解。

ArrayList和LinkedList源码请参考：

[Java集合(四)--基于JDK1.8的ArrayList源码解读][Java_--_JDK1.8_ArrayList]

[Java集合(五)--LinkedList源码解读][Java_--LinkedList]

本文我们会学习：单链表、双端链表、有序链表、双向链表和有迭代器的链表，并且会讲解一下抽象数据类型（ADT）的思想，如何用 ADT 描述

栈和队列，如何用链表代替数组来实现栈和队列。

#### 链节点： ####

在链表中，每个元素都被包含在链节点Link中。一个链节点是某个类的对象，这个类可以叫做Link。每个Link对象都包含对下一个Link引用的

字段（通常叫next）。但是链表本身有个字段指向对第一个Link的引用。

![1351999-20190624172332111-1246445382.png][]

代码示例：

public class Link {
        private Object data;
        private Link next;
    }

#### 单链表： ####

单链表的机构比较简单，每个Node包含data和next(指向下个Node)，最后一个Node的next指向null

图例：

![1351999-20190625104738505-656053797.png][]

代码实现：

public class SingleLinkList<E> {
        private int size;   //链表长度大小
        private Node head;  //头结点
    
        public SingleLinkList() {
            size = 0;
            head = null;
        }
    
        //添加元素到head
        public void addFirst(E data) {
            Node newNode = new Node(data);
            if (size == 0) {
                head = newNode;
            } else {
                newNode.next = head;
                head = newNode;
            }
            size++;
        }
    
        //删除头结点
        public E deleteFirst() {
            final E data = (E)head.data;
            head = head.next;
            size--;
            return data;
        }
    
        //查询某个元素是否存在
        public E find(E object) {
            Node current = head;
            int tempSize = size;
            while (tempSize > 0) {
                if (object == current.data) {
                    return (E)current.data;
                } else {
                    current = current.next;
                }
                tempSize--;
            }
            return null;
        }
    
        //删除链表中某个元素
        public boolean delete(E object) {
            if (null != object) {
                Node current = head;
                Node previous = head;
                while (!object.equals(current.data)) {
                    if (current.next == null) {
                        return false;
                    } else {
                        previous = current;
                        current = current.next;
                    }
                }
                if (current == head) {
                    head = current.next;
                } else {
                    previous.next = current.next;
                }
                size--;
            }
            return true;
    
        }
    
        //遍历打印链表
        public void displayList() {
            Node current = head;
            int tempSize = size;
            if (tempSize == 0) {
                System.out.print("[]");
            } else {
                System.out.print("[");
                while (current != null) {
                    if (current.next == null) {
                        System.out.print(current.data);;
                    } else {
                        System.out.print(current.data + "-->");;
                    }
                    current = current.next;
                }
                System.out.println("]");
            }
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        private static class Node<E>{
            E data;
            Node<E> next;
            Node(E data) {
                this.data = data;
            }
        }
    }

public static void main(String[] args) {
        
        SingleLinkList<Integer> singleList = new SingleLinkList<Integer>();
        singleList.addFirst(22);   //添加节点
        singleList.addFirst(44);
        singleList.addFirst(66);
        singleList.addFirst(88);
        singleList.displayList();   //打印链表结构
        singleList.delete(44); 　　//删除某个节点
        singleList.displayList();
        System.out.println(singleList.find(66));   //查询某个节点
    }

打印结果：
    [88-->66-->44-->22]
    [88-->66-->22]
    66

#### 双端链表： ####

双端链表和单向链表很相似，但是增加了一个新特性：就是对最后一个节点的引用，最后一个节点定义为tail

PS：双端链表不是双向链表，只能单向遍历，只是可以在双端添加/删除数据

图例：

![1351999-20190625134540791-1135026937.png][]

代码实现：

public class DoubleLinkList<E> {
        private int size;   //链表长度大小
        private Node head;  //头结点
        private Node tail;  //尾结点
    
        public DoubleLinkList() {
            size = 0;
            head = null;
            tail = null;
        }
    
        //添加元素到head
        public void addFirst(E data) {
            Node newNode = new Node(data);
            if (size == 0) {
                head = newNode;
                tail = newNode;
            } else {
                newNode.next = head;
                head = newNode;
            }
            size++;
        }
    
        //添加元素到tail
        public void addLast(E data) {
            Node newNode = new Node(data);
            if (size == 0) {
                head = newNode;
                tail = newNode;
            } else {
                tail.next = newNode;
                tail = newNode;
            }
            size++;
        }
    
        //删除头结点
        public E deleteFirst() {
            if (isEmpty()) {
                return null;
            }
            final E data = (E)head.data;
            if (head.next == null) {
                tail = null;
            }
            head = head.next;
            size--;
            return data;
        }
    
        //删除尾结点
        public E deleteLast() {
            if (isEmpty()) {
                return null;
            }
            final E data = (E)tail.data;
            if (head.next == null) {
                head = null;
            }
            int tempSize = size;
            Node current = head;
            Node previous = head;
            while (tempSize > 0) {
                if (current.next == null) {
                    previous.next = null;
                    break;
                }
                previous = current;
                current = current.next;
                tempSize--;
            }
            tail = previous;
            size--;
            return data;
        }
    
        //查询某个元素是否存在
        public E find(E object) {
            Node current = head;
            int tempSize = size;
            while (tempSize > 0) {
                if (object == current.data) {
                    return (E)current.data;
                } else {
                    current = current.next;
                }
                tempSize--;
            }
            return null;
        }
    
        //删除链表中某个元素
        public boolean delete(E object) {
            if (null != object) {
                Node current = head;
                Node previous = head;
                while (!object.equals(current.data)) {
                    if (current.next == null) {
                        return false;
                    } else {
                        previous = current;
                        current = current.next;
                    }
                }
                if (current == head) {
                    head = current.next;
                }else {
                    previous.next = current.next;
                }
                size--;
            }
            return true;
    
        }
    
        //遍历打印链表
        public void displayList() {
            Node current = head;
            int tempSize = size;
            if (tempSize == 0) {
                System.out.print("[]");
            } else {
                System.out.print("[");
                while (current != null) {
                    if (current == tail) {
                        System.out.print(current.data);
                        break;
                    } else {
                        System.out.print(current.data + "-->");
                    }
                    current = current.next;
                }
                System.out.println("]");
            }
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        private static class Node<E>{
            E data;
            Node<E> next;
            Node(E data) {
                this.data = data;
            }
        }
    }

public static void main(String[] args) {
    	DoubleLinkList<Integer> doubleLinkList = new DoubleLinkList<Integer>();
    	doubleLinkList.addFirst(22);   //添加节点
    	doubleLinkList.addFirst(44);
    	doubleLinkList.addLast(66);
    	doubleLinkList.addLast(88);
    	doubleLinkList.addFirst(101);
    	doubleLinkList.displayList();   //打印链表结构
    	doubleLinkList.delete(44); //删除某个节点
    	doubleLinkList.displayList();
    	doubleLinkList.deleteLast();    //删除尾节点
    	doubleLinkList.displayList();
    	doubleLinkList.deleteFirst();   //删除头结点
    	doubleLinkList.displayList();
    	System.out.println(doubleLinkList.find(66));   //查询某个节点
    }

输出结果：
    [101-->44-->22-->66-->88]
    [101-->22-->66-->88]
    [101-->22-->66]
    [22-->66]
    66

链表的效率：

表头插入和删除的速度很快，时间复杂度O(1)

平均下来，定点插入、删除、查询都需要搜索链表中一半的节点，需要O(N)次比较，相比而言，数组执行这些操作也需要O(N)次比较，但是

链表不需要移动数据，只需要改变前后引用，而数组只能整体复制，效率会好很多

链表的另一个优点体现在内存使用上，需要多少内存就使用多少内存，而数组一开始的内存空间都是确定的

#### 有序链表： ####

对于某些应用来说，在链表中保持数据的有序很很有用的。有序链表中，数据都是按照关键值有序排列的。

在大多数使用有序数组的场景也可以使用有序链表，在插入速度方面有很大优势

有序链表和一般单向链表只是添加方法有区别，其余方法都是相同的

代码示例：

public class SortedLinkList {
        private int size;   //链表长度大小
        private Node head;  //头结点
    
        public SortedLinkList() {
            size = 0;
            head = null;
        }
    
        //添加元素
        public void add(int data) {
            Node newNode = new Node(data);
            Node previoue = null;
            Node current = head;
            while (current != null && data > current.data) {
                previoue = current;
                current = current.next;
            }
            if (previoue == null) {
                head = newNode;
                head.next = current;
            } else {
                previoue.next = newNode;
                newNode.next = current;
            }
            size++;
        }
    
        //删除头结点
        public int deleteFirst() {
            final int data = head.data;
            head = head.next;
            size--;
            return data;
        }
    
        //查询某个元素是否存在
        public int find(int object) {
            Node current = head;
            int tempSize = size;
            while (tempSize > 0) {
                if (object == current.data) {
                    return current.data;
                } else {
                    current = current.next;
                }
                tempSize--;
            }
            return -1;
        }
    
        //删除链表中某个元素
        public boolean delete(int object) {
            Node current = head;
            Node previous = head;
            while (object != current.data) {
                if (current.next == null) {
                    return false;
                } else {
                    previous = current;
                    current = current.next;
                }
            }
            if (current == head) {
                head = current.next;
            } else {
                previous.next = current.next;
            }
            size--;
            return true;
    
        }
    
        //遍历打印链表
        public void displayList() {
            Node current = head;
            int tempSize = size;
            if (tempSize == 0) {
                System.out.print("[]");
            } else {
                System.out.print("[");
                while (current != null) {
                    if (current.next == null) {
                        System.out.print(current.data);;
                    } else {
                        System.out.print(current.data + "-->");;
                    }
                    current = current.next;
                }
                System.out.println("]");
            }
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        private static class Node{
            int data;
            Node next;
            Node(int data) {
                this.data = data;
            }
        }
    }

public static void main(String[] args) {
    	SortedLinkList sortedLinkList = new SortedLinkList();
    	sortedLinkList.add(5);   //添加节点
    	sortedLinkList.add(1);
    	sortedLinkList.add(8);
    	sortedLinkList.add(2);
    	sortedLinkList.add(101);
    	sortedLinkList.displayList();   //打印链表结构
    	sortedLinkList.delete(8); //删除某个节点
    	sortedLinkList.displayList();
    	sortedLinkList.deleteFirst();   //删除头结点
    	sortedLinkList.displayList();
    	System.out.println(sortedLinkList.find(101));   //查询某个节点
    }

输出结果：
    [1-->2-->5-->8-->101]
    [1-->2-->5-->101]
    [2-->5-->101]
    101

#### 双向链表： ####

双向链表就是为了解决单向链表只能单向遍历而效率慢的问题，因为只能current=current.next进行遍历，只能获得下一个节点，而不能

获取上一个节点

在学习LinkedList源码的时候，我们已经详细了解过双向链表了，[Java集合(五)--LinkedList源码解读][Java_--LinkedList]

图例：

![1351999-20190625144223606-1712129914.png][]

代码示例：

public class DoubleLinkedList<E> {
        private int size;   //链表长度大小
        private Node head;  //头结点
        private Node tail;  //尾结点
    
        public DoubleLinkedList() {
            size = 0;
            head = null;
            tail = null;
        }
    
        //添加元素到head
        public void addFirst(E data) {
            Node newNode = new Node(data);
            if (size == 0) {
                tail = newNode;
            } else {
                head.previous = newNode;
                newNode.next = head;
            }
            head = newNode;
            size++;
        }
    
        //添加元素到tail
        public void addLast(E data) {
            Node newNode = new Node(data);
            if (size == 0) {
                head = newNode;
            } else {
                tail.next = newNode;
                newNode.previous = tail;
            }
            tail = newNode;
            size++;
        }
    
        //删除头结点
        public E deleteFirst() {
            if (isEmpty()) {
                return null;
            }
            final E data = (E)head.data;
            if (head.next == null) {
                tail = null;
            }
            head = head.next;
            head.previous = null;
            size--;
            return data;
        }
    
        //删除尾结点
        public E deleteLast() {
            if (isEmpty()) {
                return null;
            }
            final E data = (E)tail.data;
            if (head.next == null) {
                head = null;
            }
            tail = tail.previous;
            tail.next = null;
            size--;
            return data;
        }
    
        //查询某个元素是否存在
        /*public E find(E object) {
            if (object == null) {
                for (Node<E> x = head; x != null; x = x.next) {
                    if (x.data == null) {
                        return x.data;
                    }
                }
            } else {
                for (Node<E> x = head; x != null; x = x.next) {
                    if (object.equals(x.data)) {
                        return x.data;
                    }
                }
            }
            return null;
        }*/
    
        //查询某个索引下标的数据
        public E find(int index) {
            return (E)node(index).data;
        }
    
        //删除链表中某个元素
        public boolean delete(E object) {
            if (object == null) {
                for (Node<E> x = head; x != null; x = x.next) {
                    if (x.data == null) {
                        unlink(x);
                        return true;
                    }
                }
            } else {
                for (Node<E> x = head; x != null; x = x.next) {
                    if (object.equals(x.data)) {
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
    
        }
    
        E unlink(Node<E> x) {
            final E element = x.data;
            final Node<E> next = x.next;
            final Node<E> prev = x.previous;
    
            if (prev == null) {
                head = next;
            } else {
                prev.next = next;
                x.previous = null;
            }
    
            if (next == null) {
                tail = prev;
            } else {
                next.previous = prev;
                x.next = null;
            }
    
            x.data = null;
            size--;
            return element;
        }
    
        Node node(int index) {
            if (index < (size >> 1)) {
                Node x = head;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
                Node<E> x = tail;
                for (int i = size - 1; i > index; i--)
                    x = x.previous;
                return x;
            }
        }
    
        //遍历打印链表
        public void displayList() {
            Node current = head;
            int tempSize = size;
            if (tempSize == 0) {
                System.out.print("[]");
            } else {
                System.out.print("[");
                while (current != null) {
                    if (current == tail) {
                        System.out.print(current.data);
                        break;
                    } else {
                        System.out.print(current.data + "-->");
                    }
                    current = current.next;
                }
                System.out.println("]");
            }
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        private static class Node<E>{
            E data;
            Node<E> previous;
            Node<E> next;
            Node(E data) {
                this.data = data;
            }
        }
    }

public static void main(String[] args) {
    	DoubleLinkedList<Integer> doubleLinkList = new DoubleLinkedList<Integer>();
    	doubleLinkList.addFirst(22);   //添加节点
    	doubleLinkList.addFirst(44);
    	doubleLinkList.addLast(66);
    	doubleLinkList.addLast(88);
    	doubleLinkList.addFirst(101);
    	doubleLinkList.displayList();   //打印链表结构
    	doubleLinkList.delete(44); //删除某个节点
    	doubleLinkList.displayList();
    	doubleLinkList.deleteLast();    //删除尾节点
    	doubleLinkList.displayList();
    	doubleLinkList.deleteFirst();   //删除头结点
    	doubleLinkList.displayList();
    	System.out.println(doubleLinkList.find(66));   //查询某个节点
    	System.out.println(doubleLinkList.find(33));   //查询某个节点
    }

输出结果：
    [101-->44-->22-->66-->88]
    [101-->22-->66-->88]
    [101-->22-->66]
    [22-->66]
    66

#### 拓展1、用链表实现： ####

public class MyStackByLinkedList<E> {
        private SingleLinkList linkList;
    
        public MyStackByLinkedList() {
            linkList = new SingleLinkList();
        }
    
        public void push(E e) {
            linkList.addFirst(e);
        }
    
        public E pop(){
            E e = (E)linkList.deleteFirst();
            return e;
        }
    
    }

#### 拓展2：用双端链表实现队列 ####

public class MyQueueByLinkedList<E> {
        private DoubleLinkedList linkedList;
    
        public MyQueueByLinkedList() {
            linkedList = new DoubleLinkedList();
        }
    
        public void add(E e) {
            linkedList.addFirst(e);
        }
    
        //移除数据
        public E remove(){
            return (E)linkedList.deleteFirst();
        }
    
    }

内容参考：<Java数据结构和算法>

转载于:https://www.cnblogs.com/huigelaile/p/11078109.html

[Java_--_JDK1.8_ArrayList]: https://www.cnblogs.com/huigelaile/p/11052997.html
[Java_--LinkedList]: https://www.cnblogs.com/huigelaile/p/11059257.html
[1351999-20190624172332111-1246445382.png]: /images/20211105/ec38d68d0d1c427b9b8f437c50e5cd65.png
[1351999-20190625104738505-656053797.png]: /images/20211105/f5091a36448f4622b657b5feb01b6912.png
[1351999-20190625134540791-1135026937.png]: /images/20211105/77b2ea32390c4e7c92c9fa9a8e7da41d.png
[1351999-20190625144223606-1712129914.png]: /images/20211105/a542e482efc043958bc7dd05b9301925.png