数据结构--链表和递归

时间：2024-03-08 10:42:19

前面我们所学习的线性数据结构

1、动态数组

2、栈

3、队列

它们的底层都是依托于静态的数组所实现：靠resize解决固定容量的问题

一、链表

1、链表：真正的动态数据结构

 优点：不需要处理固定容量的问题，是真正的动态数据结构

缺点：丧失了随机访问的能力

2、创建Node

class Node<T> {
        T data; //结点本身的数据
        Node next; // 指向下个结点

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

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

3、对链表进行增加操作

<1>链表头添加元素

<2>在链表中间添加元素

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

<3> 在链表的尾部添加元素

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

注意： 添加完成后，需要更新头节点

5、链表的属性和方法

 //链表相关的属性和方法
    private Node head; //链表的头

    private int size; //表示链表中有多少个结点

    public SelfLinkedList() {
        //创建一个虚拟头结点
        Node dummyHead = new Node(Integer.MIN_VALUE);
        this.head = dummyHead;
        this.size = 0;
    }

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

    //向链表中添加结点
    //在头部添加
    public void addHead(T data) {
        add(0, data);
    }

    //在尾部添加
    public void addTail(T data) {
        add(this.size, data);
    }

    /* public void add(int index,T data){
         //判断index 位置是否有效
         if (index < 0 || index > this.size){
             throw new IllegalArgumentException("index is invaild");
         }

         //1、创建一个结点
         Node node = new Node(data);

         //特殊处理1，如果索引为0
         if (index == 0){
             this.head = new Node(data,this.head);
             this.size++;
             return;
         }


         //2、找前驱结点
         Node pre = this.head;
         for (int i = 1; i < index; i++) {
             pre = pre.next;
         }
         //3、开始进行结点的连接
         node.next = pre.next;
         pre.next = node;
         this.size++;
     }*/
    //在任意位置添加
    public void add(int index, T data) {
        //判断index 位置是否有效
        if (index < 0 || index > this.size) {
            throw new IllegalArgumentException("index is invaild");
        }

        //1、创建一个结点
        Node node = new Node(data);

        //2、找前驱结点
        Node pre = this.head;
        for (int i = 1; i <= index; i++) {
            pre = pre.next;
        }
        //3、开始进行结点的连接
        node.next = pre.next;
        pre.next = node;
        this.size++;
    }

    //重写toString , 打印整个链表中的元素
    @Override
    public String toString() {
        //从this.head 开始一直向后找
        Node curNode = this.head.next;
        StringBuilder sb = new StringBuilder();
        while (curNode != null) {
            sb.append(curNode.data + "--->");
            curNode = curNode.next;
        }
        sb.append("null");
        return sb.toString();
    }

    //从链表中查找指定的元素是否存在
    public boolean contains(T data) {
        //遍历链表时，头结点不能动
        Node curNode = this.head.next;
        while (curNode != null) {
            if (curNode.data.equals(data)) {
                return true;
            }
            curNode = curNode.next;
        }
        return false;
    }

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

    //获取链表的头结点
    public Optional getFirst() {
        if (this.head.next == null) {
            return Optional.empty();
        }
        return Optional.ofNullable(this.head.next.data);
    }

    //获取链表的尾结点
    public Optional<T> getLast() {
        if (this.head.next == null) {
            return Optional.empty();
        }
        //遍历链表时，头结点不能动
        Node<T> curNode = this.head;
        while (curNode.next != null) {
            curNode = curNode.next;
        }
        return Optional.of(curNode.data);
    }

    //从链表中获取任意位置的头结点
    public T get(int index) {
        if (index < 0 || index >= this.size) {
            throw new IllegalArgumentException("index is invalid");
        }
        Node<T> curNode = this.head.next;
        int i = 0;
        while (i < index) {
            curNode = curNode.next;
            i++;
        }
        return curNode.data;
    }

    // 从链表的头部删除元素
    public T removeHead() {
        if (this.isEmpty()) {
            return null;
        }
        Node<T> delNode = this.head.next;
        this.head.next = delNode.next;
        delNode.next = null;
        //更新size
        this.size--;
        return delNode.data;
    }

    // 从链表的尾部去删除元素
    public T removeTail() {
        if (this.isEmpty()) {
            return null;
        }
        Node<T> pre = this.head;
        while (pre.next.next != null) {
            pre = pre.next;
        }
        Node<T> delNode = pre.next;
        pre.next = delNode.next;
        delNode.next = null;
        //更新size
        this.size--;
        return delNode.data;
    }

    public void remove2(T val){
        //更新头结点
       this.head.next = recusionRemove(this.head.next,val);
    }

    // 使用递归的方式从链表中删除元素
    // 递归函数的语义，从以node为头结点的链表中删除元素value，返回值为删除之后链表的头结点
    private Node recusionRemove(Node node, T value) {
        //递归终止的条件
        if (node == null) {
            return null;
        }
        //递归操作
        if (node.data.equals(value)) {
            this.size--;
            return node.next;
        } else {
            node.next = recusionRemove(node.next, value);
            return node;
        }
    }

    // 删除任意位置的结点
    public T remove(int index) {
        if (index < 0 || index >= this.size) {
            throw new IllegalArgumentException("index is invalid");
        }
        //找删除结点的前驱
        Node<T> pre = this.head;
        int i = 0;
        while (i < index) {
            pre = pre.next;
            i++;
        }
        Node<T> delNode = pre.next;
        pre.next = delNode.next;
        delNode.next = null;
        this.size--;
        return delNode.data;
    }

    //根据值从链表中删除元素(使用虚拟头结点)
    public int removeByValue(T val) {
        int count = 0;

        // 定义前驱结点
        Node<T> pre = this.head;
        while (pre.next != null) {
            Node<T> curNode = pre.next;
            if (curNode.data.equals(val)) {
                pre.next = pre.next.next;
                curNode.next = null;
                this.size--;
                count++;
            } else {
                pre = pre.next;
            }
        }
        return count;
    }

    //根据值从链表中删除元素(不使用虚拟头结点)
    public int removeByValue2(T val) {
        int count = 0;
        Node<T> realHead = this.head.next;

        while (realHead != null && realHead.data.equals(val)) {
            realHead = realHead.next;
            this.size--;
            count++;
        }

        //判断链表是否为空
        if (realHead == null) {
            return count;
        }

        //假设头结点不是要删除的结点
        Node pre = realHead;
        while (pre.next != null) {
            Node<T> delNode = pre.next;
            if (delNode.data.equals(val)) {
                pre.next = delNode.next;
                delNode.next = null;
                this.size--;
                count++;
            } else {
                pre = pre.next;
            }
        }
        return count;
    }

6、从链表中删除元素

7、链表的时间复杂度分析

八、使用链表实现栈

  以链表作为栈的底层数据结构。

public class LinkedStack<T> implements Stack_I<T> {

    private SelfLinkedList<T> data;

    public LinkedStack(){
        this.data = new SelfLinkedList<>();
    }

    @Override
    public void push(T ele) {
        this.data.addHead(ele);
    }

    @Override
    public T pop() {

        try {
            return this.data.removeHead();
        } catch (Exception e) {
            return null;
        }
    }

    @Override
    public T peek() {
        return this.data.getFirst().orElse(null);
    }

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

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

相关文章