05-链表 LinkedList

1、线性数据结构

2、链表简介

• 最简单的动态数据结构，
• 线性的数据结构
• 更深入的理解引用(或者指针)
• 更深入的理解递归
• 辅助组成其他数据结构
• 数据存储在“节点”（Node）中，节点会指向下一个节点
• 链表也有长度，最后一个节点指向null

• 优点：真正的动态，不需要处理固定容量的问题
• 缺点：丧失了随机访问的能力

3、链表的实现

内部私有化一个Node类，存有当前节点的值和当前节点指向的的下一个节点。

显而易见，最后一个节点指向null

private class Node {
    
	E e;
	Node next;
}

3.1、从链表头部添加元素

添加元素的方向：从链表头部添加元素，更方便，只需让新节点的next指向原链表的头节点即可。

3.2、链表中间插入元素

在链表某索引处插入一个元素，需要找到该索引的前一个节点prev。

之后：让新添加节点指向prev原来指向的节点；再改变prev的指向：指向新添加节点。

存在的问题：索引0不适用，即头节点prev节点；头节点需要另外的判断处理。

3.3、优化——为链表设立虚拟头结点

在插入元素时，首先需要判断一下是否为头节点。这样判断不够优雅，可以进行优化。

dummyHead的引入并不会打乱原来的添加逻辑，只会简化原有逻辑。

如下图，此时真正的头节点为dummyHead的next，dummyHead是一个虚拟节点，数据为null即可，对外不可知。

3.4、删除链表中的元素

同添加操作相同，使用虚拟头节点可以简化删除逻辑。

3.5、代码

package linkedList;

public class LinkedList<E> {

    //节点
    private class Node{

        public E e;
        public Node next;

        public Node(E e, Node next) {

            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {

            this.e = null;
            this.next = null;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    //虚拟头节点
    private Node dummyHead;
    int size;

    public LinkedList() {

        dummyHead = new Node();
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public void add2Head(E e){
        add(0, e);
    }

    public void add2Last(E e){
        add(size, e);
    }

    //在链表的index位置添加新的元素，范围：第一个元素前一个，最后一个元素后一个
    //在链表中不是一个常用的操作
    //添加操作，涉及到索引前后的数据，prev处理起来很有效果
    public void add(int index, E e){

        if(index<0 || index>size){
            throw new IllegalArgumentException("索引不合法");
        }

        Node prev = dummyHead;
        for(int i=0; i<index; i++){
            prev = prev.next;
        }

//        Node node = new Node(e);
//        node.next = prev.next;
//        prev.next = node;
        prev.next = new Node(e, prev.next);
        size++;
    }

    public E getHead(){
        return get(0);
    }

    public E getLast(){
        return get(size-1);
    }

    public E get(int index){

        if(index<0 || index>size){
            throw new IllegalArgumentException("获取失败，索引不合法");
        }

        Node cur = dummyHead.next;
        for(int i=0; i<index; i++){
            cur = cur.next;
        }
        return cur.e;
    }

    public void set(int index, E newE){

        if(index<0 || index>size){
            throw new IllegalArgumentException("修改失败，索引不合法");
        }

        Node cur = dummyHead.next;
        for(int i=0; i<index; i++){
            cur = cur.next;
        }
        cur.e = newE;
    }

    public E remove(int index){

        Node prev = dummyHead;
        for(int i=0; i<index; i++){
            prev = prev.next;
        }

        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size--;

        return retNode.e;
    }

    public E removeLast(){
        return remove(size-1);
    }

    public E removeHead(){
        return remove(0);
    }

    public void removeElement(E e){

        Node prev = dummyHead;
        while (prev.next != null){
            if(prev.next.e.equals(e)){
                break;
            }
            prev = prev.next;
        }

        if(prev.next != null){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
        }
    }

    public boolean contains(E e){

        Node cur = dummyHead.next;
        while(cur != null){
            if(cur.e.equals(e)){
                return true;
            }
        }
        return false;
    }

    @Override
    public String toString() {

        StringBuilder builder = new StringBuilder();

        Node cur = dummyHead.next;
        while(cur!=null){
            builder.append(cur+"->");
            cur = cur.next;
        }
        builder.append("NULL");

        return builder.toString();
    }
}

3.6链表的时间复杂度分析

4、基于链表的栈

分析链表的时间复杂度，易知，链表很容易实现栈的特性：从一端添加也从同一端删除，只有头节点对外暴露。

数组栈是一个静态栈，而链表栈是一个静态栈，在push时不存在扩容复制，但是链表栈会在push时会new对象。

4.1、代码

package stack;

import linkedList.LinkedList;

public class LinkedListStack<T> implements Stack<T> {

    private LinkedList<T> linkedList;

    public LinkedListStack() {
        linkedList = new LinkedList<>();
    }

    @Override
    public int getSize() {
        return linkedList.getSize();
    }

    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    @Override
    public void push(T t) {
        linkedList.addToHead(t);
    }

    @Override
    public T pop() {
        return linkedList.removeHead();
    }

    @Override
    public T peek() {
        return linkedList.getHead();
    }

    @Override
    public String toString() {

        StringBuilder builder = new StringBuilder();
        builder.append("Stack: top ");
        builder.append(linkedList);
        return builder.toString();
    }
}

4.2、测试

比对数组栈与链表栈：运行时间与次数有关。

@Test
public void ArrayVsLoop(){

    ArrayStack<Integer> arrayStack = new ArrayStack<>();
    LinkedListStack<Integer> listStack = new LinkedListStack<Integer>();

    int arrayTime = getRunTime(10000000, arrayStack);
    int listTime = getRunTime(10000000, listStack);

    System.out.printf("数组栈的执行时间是：%d毫秒\n",arrayTime);
    System.out.printf("链表栈的执行时间是：%d毫秒\n",listTime);
}

private int getRunTime(int times, Stack<Integer> stack){

    long startTime = System.currentTimeMillis();

    Random random = new Random();

    for(int i=0; i<times; i++){
        stack.push(random.nextInt(Integer.MAX_VALUE));
    }
    for(int i=0; i<times; i++){
        stack.pop();
    }
    long endTime = System.currentTimeMillis();
    long time = endTime - startTime;
    return (int)time;
}

5、基于链表的队列

因为队列是FIFO，所以基础的链表模型并不适用于作为队列底层。改进链表模型：在链表中增加一个tail节点。

队列：基于链表的节点，从tail入队，head出队。

5.1、代码

package queue.linkedListQueue;

import queue.arrayQueue.Queue;

public class LinkedListQueue<T> implements Queue<T> {

    //节点
    private class Node{
        public T t;
        public Node next;

        public Node(T t, Node next) {
            this.t = t;
            this.next = next;
        }

        public Node(T t) {
            this(t, null);
        }

        public Node() {
            this.t = null;
            this.next = null;
        }

        @Override
        public String toString() {
            return t.toString();
        }
    }

    private Node head, tail;
    private int size;

    public LinkedListQueue() {
        
        head = tail = null;
        size = 0;
    }

    @Override
    public void enqueue(T t) {

        if(isEmpty()){
            tail = new Node(t);
            head = tail;
        }else {
            tail.next = new Node(t);
            tail = tail.next;
        }
        size++;
    }

    @Override
    public T dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("出对失败，队列为空");
        }
        Node retNode = head;
        head = head.next;
        retNode.next = null;
        if(head==null){
            tail = null;
        }
        size--;
        return retNode.t;
    }

    @Override
    public T getFront() {
        return head.t;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public String toString() {

        StringBuilder builder = new StringBuilder();
        builder.append("Queue: front ");

        Node cur = head;
        while (cur != null){
            builder.append(cur+"->");
            cur = cur.next;
        }
        builder.append("NULL tail");
        return builder.toString();
    }
}

5.2、测试

比对循环队列与链表队列：运行时间与次数有关。

public static void main(String[] args) {
    LoopQueue<Integer> loopQueue = new LoopQueue<>();
    LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();

    int loopTime = getRunTime(100000, loopQueue);
    int linkedListTime = getRunTime(100000, linkedListQueue);

    System.out.printf("循环队列的执行时间是：%d毫秒\n",loopTime);
    System.out.printf("链表队列的执行时间是：%d毫秒\n",linkedListTime);
}

private static int getRunTime(int times, Queue<Integer> queue){

    long startTime = System.currentTimeMillis();

    Random random = new Random();

    for(int i=0; i<times; i++){
        queue.enqueue(random.nextInt(Integer.MAX_VALUE));
    }
    for(int i=0; i<times; i++){
        queue.dequeue();
    }
    long endTime = System.currentTimeMillis();
    long time = endTime - startTime;
    return (int)time;
}

6、其他形态的链表

6.1、双链表

6.2、循环链表

6.3、数组链表

7、Java中的链表

LinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    
}

API接口

05-链表 LinkedList

原文：https://www.cnblogs.com/sout-ch233/p/13069640.html