数据结构-列表LinkedList

一,链表的简单的认识.

数组,栈,队列是线性数据结构,但都算不上是动态数据结构,底层都是依托静态数组,但是链表是确实真正意义上的动态数组.

为什么要学习链表?

1,链表时最简单的动态数据结构

2,掌握链表有助于学习更复杂的数据结构,例如,二叉树,trie.

3,学习链表有助于更深入的理解引用和递归,

1,链表

2,创建Node

二,链表的方法

1,对链表添加操作

(1)链表头添加元素

(2)链表中间添加元素

关键点：找到要待添加位置的前一个结点

(3)向链表尾部添加元素

添加完成后

总结:

1,先创建节点node

2,找到最后一个节点pre

3,pre.next=node

2,使用虚拟头结点（解决在头部添加结点的特殊处理）

(注意:添加完成之后需要更新头节点)

3,链表的遍历,查询和更新操作

addHead() 向头部添加节点

addTail() 向尾部添加节点

add() 添加节点,默认头结点

get(index) 获取指定位置的节点

getFirst() 获取头节点

getLast() 获取尾节点

getSize() 获取索引

isEmpty() 判断链表是否为空

contains(val) 判断链表是否存在给定节点

toString() 遍历链表

4,从链表中删除元素

5,链表的时间复杂度分析

(1) 添加元素

(2) 删除操作

(4)修改操作

(5)查找操作

三,用代码实现链表

(需要注意的是用内部类,解决链表的数据类型(节点--Node))

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

/**
 * 链表：真正的动态数据结构
 */
public class LinkedList<T> {
    // 定义结点
    private class Node {
        T val; // 结点的值
        Node next; // 表示下一个结点

        public Node(T val) {
            this.val = val;
        }

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


    // 链表的头结点
    private Node header;
    private int size;

    // 构造链表
    public LinkedList() {
        this.header = null;
        this.size = 0;
    }

    // 判断链表是否为空
    public boolean isEmpty() {
        return this.size == 0;
    }

    // 获取链表中元素的个数
    public int getSize() {
        return this.size;
    }

    // 向链表中添加元素

    /**
     * 在链表的头部添加
     */
    public void addHeader(T val) {
        add(0, val);
    }

    /**
     * 在链表的尾部添加
     */
    public void addTail(T val) {
        add(this.size, val);
    }

    // 在任意位置添加
    /*public void add(int index, T val) {
        if (index < 0 || index > this.size) {
            throw new IllegalArgumentException("index is invalid!");
        }

        // 1、创建结点
        Node node = new Node(val);
        // 特殊处理：头结点,为啥？头结点没有前驱
        if (index == 0) {
            this.header = node;
            this.size++;
            return;
        }
        // 2、找到插入位置的前驱pre
        Node pre = this.header;
        int count = 1;
        while (count < index) {
            pre = pre.next;
            count++;
        }
        // 3、改变索引的指向
        node.next = pre.next;
        pre.next = node;
        // 4、更新size
        this.size++;
    }*/

    public void add(int index, T val) {
        if (index < 0 || index > this.size) {
            throw new IllegalArgumentException("index is invalid!");
        }
        // 0、创建结点，作为头结点的前驱
        Node dummyHead = new Node(null);
        dummyHead.next = this.header;
        // 1、创建结点
        Node node = new Node(val);
        // 2、找前驱结点
        Node pre = dummyHead;
        int count = 1;
        while (count <= index) {
            pre = pre.next;
            count++;
        }
        // 3、改变索引的指向
        node.next = pre.next;
        pre.next = node;
        // 4、更新size
        this.size++;
        // 5、更新头结点
        this.header = dummyHead.next;
    }

    @Override
    public String toString() {
        List<String> result = new ArrayList<>();
        // 遍历链表
        Node cur = this.header;
        while (cur != null) {
            result.add(cur.val.toString() + "----->");
            cur = cur.next;
        }
        return result.stream().collect(Collectors.joining());
    }

    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 1; i <= 10; i++) {
            Random random = new Random();
            int val = random.nextInt(1000) + 1;
            System.out.println(val);
            linkedList.addHeader(val);
            System.out.println(linkedList);
        }
        linkedList.add(10,249);
        System.out.println(linkedList);
    }
}

四,使用链表实现队列

基本掌握链表的功能,就可以尝试着用链表实现栈或者队列,我们之前用的底层数据类型时数组.

// 定义节点类
class Node {
    int data;
    Node next;

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

// 定义栈类
class Stack {
    private Node top;

    public Stack() {
        this.top = null;
    }

    public void push(int data) {
        Node newNode = new Node(data);
        if (top == null) {
            top = newNode;
        } else {
            newNode.next = top;
            top = newNode;
        }
    }

    public int pop() {
        if (top == null) {
            throw new EmptyStackException();
        } else {
            int data = top.data;
            top = top.next;
            return data;
        }
    }
}

// 定义队列类
class Queue {
    private Node front;
    private Node rear;

    public Queue() {
        this.front = null;
        this.rear = null;
    }

    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (rear == null) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    public int dequeue() {
        if (front == null) {
            throw new NoSuchElementException();
        } else {
            int data = front.data;
            front = front.next;
            if (front == null) {
                rear = null;
            }
            return data;
        }
    }
}

上面代码演示了如何用链表实现栈和队列，分别通过Stack类和Queue类来实现。可以根据自己的需要进一步扩展这两个类的功能，以满足具体的需求。