链表

线性数据结构，典型代表：LinkedList
递归结构，数据存储在“节点”（Node）中

优点：真正的[动态数据]存储，不需要处理固定容量的问题（数据、栈、队列等不是）
缺点：但丧失了随机访问的能力（即通过索引访问数据，在内存中开辟的每一个节点的位置都不是连续的）
例子

class Node {
    E e;
    Node next;
}

时间复杂度分析
增、删、查的操作中如果只是对链表头进行操作，那么时间复杂度为O(1)，对其他位置进行操作为O(n)

自定义链表类实现LinkedList

public class LinkedList<E> {

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

    /**
     * 构造方法
     */
    public LinkedList() {
        this.dummyHead = new Node(null, null);
        this.size = 0;
    }

    /**
     * 返回链表长度
     *
     * @return
     */
    public int getSize() {
        return size;
    }

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

    /**
     * 在链表头添加元素e
     * 1.把元素e转换成newNode节点
     * 2.将newNode的next指向原始的head
     * 3.原始的head指向newNode
     *
     * @param e
     */
    public void addFirst(E e) {
        add(0, e);
    }

    /**
     * 在指定位置插入元素
     * 1.把元素e转换成newNode节点
     * 2.找到指定位置的前一个节点数据prev
     * 3.将newNode的next指向prev的next，prev的next指向newNode
     *
     * @param index
     * @param e
     */
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }
        //遍历元素：初始化时 prev=head
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        /*Node newNode = new Node(e);
        newNode.next = prev.next;
        prev.next = newNode;*/
        prev.next = new Node(e, prev.next);
        size ++;
    }

    /**
     * 在链表末尾添加元素
     * @param e
     */
    public void addLast(E e){
        add(size, e);
    }

    /**
     * 获取指定位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }
        //遍历元素：此处和add时不同  add是要获取指定位置的前一个元素，get是要获取指定位置元素
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return (E) cur.e;
    }

    /**
     * 获取头节点的元素
     * @return
     */
    public E getFirst(){
        return get(0);
    }

    /**
     * 获取末尾节点的元素
     * @return
     */
    public E getLast(){
        return get(size);
    }

    /**
     * 修改指定位置节点的元素值
     * 遍历元素
     * @param index
     * @param e
     */
    public void set(int index, E e){
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }
        //遍历元素：此处和add时不同  add是要获取指定位置的前一个元素，set是要获取指定位置元素
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.e = e;
    }

    /**
     * 查看链表中是否有指定元素
     * @param e
     * @return
     */
    public boolean contains(E e){
        Node cur = dummyHead.next;
        while (cur != null){
            if(cur.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 删除指定位置的节点
     * 1.获取删除节点的前一个节点prevNode
     * 2.prevNode.next指向delNode的next
     * 3.delNode指向null
     * @param index
     */
    public E remove(int index){
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }
        //遍历获取待删除元素的前一个节点
        Node prevNode = dummyHead;
        for(int i=0; i< index; i++){
            prevNode = prevNode.next;
        }
        //获取待删除元素
        Node delNode = prevNode.next;
        //赋值
        prevNode.next = delNode.next;
        delNode.next = null;
        size --;
        return (E)delNode.e;
    }

    /**
     * 删除头节点
     * @return
     */
    public E removeFirst(){
        return remove(0);
    }

    /**
     * 删除末尾节点
     * @return
     */
    public E removeLast(){
        return remove(size -1);
    }

    @Override
    public String toString(){
        StringBuilder str = new StringBuilder();

        Node cur = dummyHead.next;
        while (cur != null){
            str.append(cur + "->");
            cur = cur.next;
        }
        return str.toString();
    }
}

使用链表来实现栈LinkedListStack

链表的这种结构就非常适合实现栈（先进后出）的结构，只对栈的一端进行操作

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

    private LinkedList<E> list;

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

    @Override
    public void push(E e) {
        list.addFirst(e);
    }

    @Override
    public E pop() {
        return list.removeFirst();
    }

    @Override
    public E peek() {
        return list.getFirst();
    }

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

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

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("Stack: top ");
        str.append(list);
        return str.toString();
    }
}

使用链表来实现队列LinkedListQueue

操作链表头的时间复杂度为O(1)，在链表中增加tail后在链表尾添加元素的时间复杂度也是O(1)(删除为O(n)) 所以使用链表尾来进元素链表头来出元素

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

    private Node head;
    private Node tail;
    private int size;

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

    /**
     * 从链表尾进数据
     * @param e
     */
    @Override
    public void enqueue(E e) {
        if(tail == null){
            tail = new Node(e);
            head = tail;
        }else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size ++;
    }

    /**
     * 从链表头出数据
     * @return
     * @throws Exception
     */
    @Override
    public E dequeue() throws Exception {
        if(isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }
        Node retNode = head;
        head = head.next;
        retNode.next = null;
        if(head == null){
            tail = null;
        }
        size --;
        return (E) retNode.e;
    }

    @Override
    public E getFront() {
        if(isEmpty()) {
            throw new IllegalArgumentException("Queue is empty.");
        }
        return (E) head.e;
    }

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

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

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");

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

递归

本质上，将原来的问题转化成更小的同一问题
1.求解最基本的问题
2.把原问题转化为更小的问题

递归函数的调用本质就是函数调用，只不过调用的函数就是自己
例子：数组求和

    /**
     * 递归方式数组求和
     * @param arr
     * @return
     */
    public static int sum(int[] arr){
        return recursive(arr, 0);
    }

    /**
     * 计算从index到最后一位的和
     * @param arr
     * @param index
     * @return
     */
    public static int recursive(int[] arr, int index){
        if(index == arr.length){
            return 0;
        }
        return arr[index] + recursive(arr, index + 1);
    }

例子：leetcode 203 删除链表中等于给定值 val 的所有节点。

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
     
    /**
     * 删除指定元素 然后返回链表集合
     * 使用递归方法实现
     * @param head
     * @param val
     * @return
     */
    public static ListNode removeElements5(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2022/01/14 11:41