首页 > 其他分享 >第2章. 链表(LinkedList)

第2章. 链表(LinkedList)

时间:2023-12-06 20:22:48浏览次数:33  
标签:Node index LinkedList int element 链表 next size

链表

链表是一种链式存储的线性表,所有元素的内存地址不一定是连续的

单向链表

一、单向链表的设计

1.1、不带虚拟头结点

public class LinkedList<E> {
    // 链表的节点数量
    private int size;
    // 链表的头结点
    private Node<E> first;

    // 静态成员内部类:static静态的、因为是成员内部类所以可以用private修饰
    private static class Node<E>{
        // 节点自身存储的元素
        E element;
        // 保存下一个节点的地址
        Node<E> next;
		
        // 因为内部类也是一个类,所以也有构造方法
        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
   // 不需要预先分配容量所以不需要写构造函数
}
1.2、带虚拟头结点

public class LinkedList<E> {
    // 链表的节点数量
    private int size;
    // 链表的头结点
    private Node<E> first;

    // 静态内部类
    private class Node<E>{
        // 节点自身存储的元素
        E element;
        // 保存下一个节点的地址
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
    // 带虚拟头节点的单链表
   	public LinkedList<E>() {
       first = new Node<E>(null, null);
   	}
}

二、链表的接口设计(学习其设计思想)

  • 左图:由于链表的大部分接口和动态数组一致,我们抽取出一个共同的List接口
  • 右图:由于链表和动态数组中有些方法的实现完全一样,我们将这些完全相同的方法放到一个抽象类中。这样ArrayList类和LinkedList类中实现完全一样的方法就在抽象类AbstractList中(抽象的父类,达到代码复用的目的),而其他方法则声明在List接口中
// 动态数组和链表中都有且实现也完全一样的方法,我们抽取到AbstractList中
1、private void rangeCheck(int index)
2、private void rangeCheckForAdd(int index)
3、public int size()
4、public boolean isEmpty()
5、public boolean contains(E element)
6、public void add(E element)
2.1、List接口
package DataStructure._02链表;

public interface List<E> {
    /**
     * 接口是抽象方法(public abstract)和常量值(public static final)定义的集合。
     */

    // 常量值
    int ELEMENT_NOT_FOUND = -1;

    // 清除所有元素
    void clear();

    // 获取index位置的元素
    E get(int index);

    // 设置index位置的元素
    E set(int index, E element);

    // 在index位置插入一个元素
    void add(int index, E element);

    // 删除index位置的元素
    E remove(int index);

    // 查看元素的索引
    int indexOf(E element);
}
2.2、AbstractList类
package DataStructure._02链表;

/**
 * @author keyongkang
 * @date 2022-07-11-8:37
 */
public abstract class AbstractList<E> implements List<E> {
    // 元素的数量。
    // 声明为protected是为了给子类使用
    protected int size;

    protected void rangeCheck(int index) {
        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
        }
    }

    protected void rangeCheckForAdd(int index) {
        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
        }
    }

    // 返回元素的数量
    public int size() {
        return size;
    }

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

    // 判断是否包含某个元素
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    // 添加元素到末尾
    public void add(E element) {
        add(size, element);
    }
}
2.3、LinkedList类
package DataStructure._02链表;

/**
 * @author keyongkang
 * @date 2022-07-10-19:27
 */
public class LinkedList<E> extends AbstractList<E> implements List {

    // 链表的头结点
    private Node<E> first;

    // 静态内部类
    private class Node<E>{
        // 节点自身存储的元素
        E element;
        // 保存下一个节点的地址
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
    
    @Override
    public void clear() {

    }

    @Override
    public E get(int index) {
        return null;
    }

    @Override
    public E set(int index, E element) {
        return null;
    }

    @Override
    public void add(int index, E element) {

    }

    @Override
    public E remove(int index) {
        return null;
    }

    @Override
    public int indexOf(E element) {
        return 0;
    }
}
2.4、ArrayList类
package DataStructure._01动态数组;

import DataStructure._02链表.AbstractList;

/**
 * @author keyongkang
 * @date 2022-07-10-10:09
 */

public class ArrayList<E> extends AbstractList<E> implements List {

    // 动态数组的所有元素
    private E[] elements;

    // 动态数组的默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    public ArrayList(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = (E[])new Object[capacity];
    }

    public ArrayList() {
        //elements = new int[DEFAULT_CAPACITY];
        this(DEFAULT_CAPACITY);
    }

    // 添加元素到动态数组index索引位置
    public void add(int index, E element) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index > size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }
        rangeCheckForAdd(index);

        // 当前动态数组的元素个数为size,我们确保需要size+1个容量
        ensureCapacity(size + 1);

        for (int i = size - 1; i >= index; i --) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size ++;
    }

    // 确保有needCapacity的容量
    private void ensureCapacity(int needCapacity) {
        // 当前容量为nowCapacity
        int nowCapacity = elements.length;
        // 当前容量大于等于所需要的容量,容量够
        if (nowCapacity >= needCapacity) return;
        // 容量不够,则扩容至1.5倍
        int newCapacity = nowCapacity + (nowCapacity >> 1);
        E[] newElements = (E[])new Object[newCapacity];

        // 拷贝元素
        for(int i = 0; i < elements.length; i ++) {
            newElements[i] = elements[i];
        }
        elements = newElements;

        System.out.println(nowCapacity + "扩容为:" + newCapacity);
    }

    // 返回index索引位置对应的元素
    public E get(int index) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index >= size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }
        rangeCheck(index);
        return elements[index];
    }

    // 删除index索引位置对应的元素,并返回所删除的元素
    public E remove(int index) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index >= size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }
        rangeCheck(index);

        // 保存要被删除的值
        E remove = elements[index];

        // 从被删除的后一个元素开始往前移动
        for (int i = index + 1; i < size; i ++) {
            elements[i - 1] = elements[i];
        }

        // (内存管理细节)将最后一个元素变为null
        elements[size - 1] = null;

        size --;

        return remove;
    }

    // 设置index位置的元素,并返回旧值
    public E set(int index, E element) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index >= size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }

        rangeCheck(index);

        // 保存当前索引的旧值
        E old = elements[index];
        // 设置index位置的新值
        elements[index] = element;

        return old;
    }

    // 查看指定元素第一次出现的位置,如果找不到则返回-1
    public int indexOf(E element) {
        // 遍历动态数组。注意size和elements.length的区别

        if (element == null) {
            for (int i = 0; i < size; i ++) {
                if (elements[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i ++) {
                if (element.equals(elements[i])) {
                    return i;
                }
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    // 清除所有元素
    public void clear() {
        //size = 0;
        // (内存管理细节)对象内存清空,但是对象数组所分配的内存还在
        for (int i = 0; i < size; i ++) {
            elements[i] = null;
        }
        size = 0;
    }

    // 打印数组
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size = ").append(size).append(", ").append("[");
        for (int i = 0; i < size; i ++) {
            if (i == size - 1) {
                sb.append(elements[i]);
                break;
            }
            sb.append(elements[i]).append(", ");
        }
        sb.append("]");

        return sb.toString();
    }
}

三、(不带虚拟头节点)单链表的常用操作

3.1、清空操作clear()

@Override
public void clear() {
    size = 0;
    first = null;
}
  • 当first指向null的时候,后面的Node将会被Java自动回收
3.2、添加操作add(int index, E element)—不带虚拟头节点

编写一个node方法用于获得index位置的节点

// node方法用于获取index位置的节点
private Node<E> node(int index) {
    rangeCheck(index);
    Node<E> cur = first;
    for (int i = 0; i < index; i ++) {
        cur = cur.next;
    }
    return cur;
}
@Override
public void add(int index, E element) {
    // 判断index是否合法
    rangeCheckForAdd(index);
    if (index == 0) {
        Node<E> newNode = new Node<>(element, first);
        first = newNode;
    } else {
        Node<E> preNode = node(index - 1);
        Node<E> newNode = new Node<>(element, preNode.next);
        preNode.next = newNode;
    }
    size ++;
}

在编写链表相关操作代码过程中,要注意边界测试,比如index = 0,size - 1,size时。先写出一般情况,然后再考虑边界问题。

3.3、删除元素remove(int index)—不带虚拟头节点

@Override
public E remove(int index) {
    rangeCheck(index);
    E delEle;
    if (index == 0) {
        delEle = first.element;
        first = first.next;
    } else {
        Node<E> preNode = node(index - 1);
        delEle = preNode.next.element;
        preNode.next = preNode.next.next;
    }
    size --;
    return delEle;
}

四、(不带虚拟头节点)单链表的相关代码

package DataStructure._02链表;

/**
 * @author keyongkang
 * @date 2022-07-10-19:27
 */
public class LinkedList<E> extends AbstractList<E> {

    // 链表的头结点
    private Node<E> first;

    // 静态内部类
    private static class Node<E>{
        // 节点自身存储的元素
        E element;
        // 保存下一个节点的地址
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }

    @Override
    public void clear() {
        size = 0;
        first = null;
    }

    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        return null;
    }

    @Override
    public void add(int index, E element) {
        // 判断index是否合法
        rangeCheckForAdd(index);
        if (index == 0) {
            Node<E> newNode = new Node<>(element, first);
            first = newNode;
        } else {
            Node<E> preNode = node(index - 1);
            Node<E> newNode = new Node<>(element, preNode.next);
            preNode.next = newNode;
        }
        size ++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        E delEle;
        if (index == 0) {
            delEle = first.element;
            first = first.next;
        } else {
            Node<E> preNode = node(index - 1);
            delEle = preNode.next.element;
            preNode.next = preNode.next.next;

        }
        size --;
        return delEle;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            Node<E> cur = first;
            for (int i = 0; i < size; i ++) {
                if (cur.element == null) return i;
                cur = cur.next;
            }
        } else {
            Node<E> cur = first;
            for (int i = 0; i < size; i ++) {
                if (element.equals(cur.element)) return i;
                cur = cur.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    // node方法用于获取index位置的节点
    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> cur = first;
        for (int i = 0; i < index; i ++) {
            cur = cur.next;
        }
        return cur;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size = ").append(size).append(", ").append("[");
        Node<E> cur = first;
        for (int i = 0; i < size; i ++) {
            if (i == size - 1) {
                sb.append(cur.element);
                break;
            }
            sb.append(cur.element).append(", ");
            cur = cur.next;
        }
        sb.append("]");

        return sb.toString();
    }
}

五、(带虚拟头结点)单链表的相关代码

为了统一头节点和非头节点的删除、添加处理逻辑,可以在最前面增加一个虚拟头节点(不存储数据)

LeeCode707. 设计链表

六、ArrayList和LinkedList的时间复杂度

  • size是数据规模n

注意:链表、添加删除那一刻的时间复杂度是O(1),整体操作平均下来是O(n)

双向链表

Java官方的LinkedList底层实现就是双向链表

一、双向链表的设计

public class DoubleLinkedList<E> extends AbstractList<E> {
    private int size;
    private Node<E> first;
    private Node<E> last;

    private static class Node<E> {
        private Node<E> prev;
        private E element;
        private Node<E> next;

        public Node(E element, Node<E> prev, Node<E> next) {
            this.element = element;
            this.prev = prev;
            this.next = next;
        }
    }
}

二、双向链表的常用操作

2.1、添加操作add(int index, E element)(重点)

@Override
public void add(int index, E element) {
    if (index == size) {
        if (size == 0) {
            first = new Node<>(null, element, null);
            last = first;
        } else {
            Node<E> prev = node(size - 1);
            Node<E> newNode = new Node<>(prev, element, null);
            prev.next = newNode;
            last = newNode;
        }
        size ++;
    } else {
        Node<E> next = node(index);
        Node<E> prev = next.prev;
        Node<E> newNode = new Node<>(prev, element, next);
        next.prev = newNode;

        if (prev == null) {
            first = newNode;
        } else {
            prev.next = newNode;
        }
        size ++;
    }
}
2.2、删除操作remove(int index)(重点)

@Override
public E remove(int index) {
    rangeCheck(index);
	
    Node<E> node = node(index);
    Node<E> prev = node.prev;
    Node<E> next = node.next;
    
    if (prev == null) { // index ==0
        first = next;
    } else {
        prev.next = next;
    }
    
    if (next == null) { // index == size - 1
        last = prev;
    } else {
        next.prev = prev;
    }
   	size --;
    return node.element;
}

思路:先写一般情况,然后再考虑左右边界优化代码

2.3、获取操作get(int index)
@Override
public int indexOf(E element) {
    Node<E> cur = null;
    if (element == null) {
        cur = first;
        for (int i = 0; i < size; i ++) {
            if (cur.element == element) return i;
            cur = cur.next;
        }
    } else {
        cur = first;
        for (int i = 0; i < size; i ++) {
            if (element.equals(cur.element)) return i;
            cur = cur.next;
        }
    }
    return ELEMENT_NOT_FOUND;
}

思路:先写一般情况,然后再考虑左右边界优化代码

Node node = new Node(index);// 当前节点

Node pre = node.prev;// 前一节点

Node next = node.next;// 后一节点

三、双向链表的相关代码

package DataStructure._02链表;

/**
 * @author keyongkang
 * @date 2022-07-12-23:04
 */
public class DoubleLinkedList<E> extends AbstractList<E> {
    private Node<E> first;
    private Node<E> last;

    private static class Node<E> {
        private Node<E> prev;
        private E element;
        private Node<E> next;

        public Node(Node<E> prev, E element, Node<E> next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
    }


    @Override
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    @Override
    public E get(int index) {
        rangeCheck(index);
        Node<E> cur = null;
        if (index < (size >> 1)) {
            cur = first;
            for (int i = 0; i < index; i ++) {
                cur = cur.next;
            }
        } else {
            cur = last;
            for (int i = size - 1; i > index; i --) {
                cur = cur.prev;
            }
        }

        return cur.element;
    }

    @Override
    public E set(int index, E element) {
        rangeCheck(index);

        return node(index).element;
    }

    @Override
    public void add(int index, E element) {
        if (index == size) {
            if (size == 0) {
                first = new Node<>(null, element, null);
                last = first;
            } else {
                Node<E> prev = node(size - 1);
                Node<E> newNode = new Node<>(prev, element, null);
                prev.next = newNode;
                last = newNode;
            }
            size ++;
        } else {
            Node<E> next = node(index);
            Node<E> prev = next.prev;
            Node<E> newNode = new Node<>(prev, element, next);
            next.prev = newNode;

            if (prev == null) {
                first = newNode;
            } else {
                prev.next = newNode;
            }
            size ++;
        }
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);

        if (index == size - 1) {
            Node<E> delNode = node(size - 1);
            last = delNode.prev;
            delNode.prev.next = null;
        } else {
            Node<E> delNode = node(index);
            if (index == 0) {
                first = delNode.next;
                delNode.next.prev = null;
            } else {
                delNode.prev.next = delNode.next;
                delNode.next.prev = delNode.prev;
            }
        }
        size --;

        return null;
    }

    @Override
    public int indexOf(E element) {
        Node<E> cur = null;
        if (element == null) {
            cur = first;
            for (int i = 0; i < size; i ++) {
                if (cur.element == element) return i;
                cur = cur.next;
            }
        } else {
            cur = first;
            for (int i = 0; i < size; i ++) {
                if (element.equals(cur.element)) return i;
                cur = cur.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }


    /**
     * 获取index位置对应的节点对象
     * @param index
     * @return
     */
    private Node<E> node(int index) {
        rangeCheck(index);

        if (index < (size >> 1)) {
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size = ").append(size).append(", ").append("[");
        Node<E> cur = first;
        for (int i = 0; i < size; i ++) {
            if (i == size - 1) {
                sb.append(cur.element);
                break;
            }
            sb.append(cur.element).append(", ");
            cur = cur.next;
        }
        sb.append("]");

        return sb.toString();
    }
}

四、双向链表vs单向链表

五、双向链表vs动态数组

单向循环链表

标签:Node,index,LinkedList,int,element,链表,next,size
From: https://www.cnblogs.com/keyongkang/p/17880445.html

相关文章

  • [LeetCode Hot 100] LeetCode19. 删除链表的倒数第N个结点
    题目描述思路一:采用两次遍历第一遍遍历先获取链表的长度length第二次从dummy节点开始走length-n步然后将该节点指向下下个节点思路二:采用一次遍历设置虚拟节点dummyHead指向head设定双指针p和q,初始都指向虚拟节点dummyHead移动q,直到p与q之间相隔的元素个数为n(即q走......
  • [LeetCode Hot 100] LeetCode21. 合并两个有序链表
    题目描述思路:新建dummy去"穿针引线"新建一个dummy节点去"穿针引线"注意最后返回的是dummy.next方法一:/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(intval){this......
  • 【实战技能】 单步运行源码分析,一期视频整明白FreeRTOS内核源码框架和运行机制,RTOS Tr
    从源码的角度来看,OS内核源码就是通过各种链表组装起来的,FreeRTOS就是下面几个链表组成的。FreeRTOS的调度,任务切换就是倒腾这几个链表。而其它的几款OS是一个链表就一撸到底了,FreeRTOS是搞了好几个。所以视频里面就重点介绍下这个,其它的支持的也做个拓展说明。搞清楚这几个链表也......
  • 深度解析C#中LinkedList<T>的存储结构
    本文承接前面的3篇有关C#的数据结构分析的文章,对于C#有关数据结构分析还有一篇就要暂时结束了,这个系列主要从Array、List、Dictionary、LinkedList、 SortedSet等5中不同类型进行介绍和分析。废话不多说,接下来我们来最后看一下这个系列的最后一种数据类型"链表"。提到链......
  • [LeetCode Hot 100] LeetCode234. 回文链表
    题目描述思路1:将值复制到数组中然后使用双指针计算链表的长度创建等长的数组将链表中的数依次放入数组中使用左右指针判断链表是否是回文链表时间复杂度:O(n)空间复杂度:O(n)思路2:快慢指针+反转链表用快慢指针,快指针走两步,慢指针走一步,快指针遇到终止位置时,慢指针就在......
  • [LeetCode Hot 100] LeetCode206. 反转链表
    题目描述思路:双指针算法方法一:/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(intval){this.val=val;}*ListNode(intval,ListNodenext){this.val=v......
  • [LeetCode Hot 100] LeetCode141. 环形链表
    题目描述思路:快慢指针slow指针:每次移动一个节点fast指针:每次移动两个节点如果链表中存在环,fast指针最终会在某一时刻追上slow指针,这是由于移动速度快的fast指针会在某个时刻绕圈并追上速度慢的slow指针条件fast!=null&&fast.next!=null保证了在每一步迭代中,fast和......
  • 链表算法笔记
    ​ 类型:单链表、双链表、循环链表操作:删除节点、添加节点        在删除节点时,C++里最好是再手动释放所删除的节点,释放内存,但是如Java、Python等语言,它们有自己的内存回收机制,就不需要手动释放了。使用虚拟头节点的原因使第一个节点和其他节点的增加和删除操作统一,......
  • 内核链表
    内核链表在很多嵌入式的代码中都有用到,因为这个链表很好用,并且代码的统一性会增强代码的可读性,因此这里简单记录一下内核链表的使用,首先是库文件,这里也就是从内核中获取的,下面的代码做了一点注释。#ifndef_LINUX_LIST_H#define_LINUX_LIST_H//include/linux/types.hstruct......
  • 链表算法总结
    知识概览链表包括单链表和双链表,这里讨论算法题中的链表。为了考虑算法题中对于时间效率的要求,链表通常是用数组模拟成静态链表的形式,速度快。单链表可以用来写邻接表(包括n个链表),邻接表可以存储树和图,最短路问题、最小生成树问题、最大流问题都可以用邻接表来存储。双链表用来......