首页 > 其他分享 >数据结构——链表

数据结构——链表

时间:2023-02-01 18:02:50浏览次数:71  
标签:Node index return cur next 链表 数据结构

链表

数组要一块连续的内存空间来存储,对内存的要求比较高。如果我们申请一个100MB大小的数组,当内存中没有连续的、足够大的存储空间 时,即便内存的剩余总可用空间大于 100MB,仍然会申请失败。

 

链表恰恰相反,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用,所以如果我们申请的是 100MB 大小的链表,根本不会有问题。

 

链表通过指针将一组零散的内存块串联在一起。其中,我们把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点 的地址。如图所示,我们把这个记录下个结点地址的指针叫作后继指针 next。

单向链表

单向链表就是通过每个节点的指针指向下一个节点从而链接起来的结构,最后一个节点的next指向null。

其中有两个结点是比较特殊的,它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点,把最后一个结点叫作尾结点。其中,头结点用来记录链表的基地址。有了它,我们就可以遍历得到整条链表。而尾结点特殊的地方是:指针 不是指向下一个结点,而是指向一个空地址 NULL,表示这是链表上最后一个结点。与数组一样,链表也支持数据的查找、插入和删除操作。只不过效率会不高。

单向循环链表

单向循环链表和单向链表的不同是,最后一个节点的next不是指向null,而是指向head节点,形成一个“环”。

循环链表是一种特殊的单链表。它跟单链表唯一的区别就在尾结点:单链表的尾结点指针指向空地址,表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。

双向链表

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。

 

双向链表包含两个指针,pre指向前一个节点,next指向后一个节点,第一个节点的pre和最后一个节点的next都指向null。

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性。

 

所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

双向循环链表

双向循环链表和双向链表的不同在于,第一个节点的pre指向最后一个节点,最后一个节点的next指向第一个节点,也形成一个“环”。而Java的LinkedList就是基于双向循环链表设计的。

代码实现

单向链表实现

public class LinkedList<E> {

    private class Node<E>{
        public E e;

        public Node<E> next;

        public Node(E e){
            this.e = e;
        }

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

    private Node<E> dummyHead;

    private Integer size;

    public LinkedList(){
        dummyHead = new Node<>(null);
        size = 0;
    }

    /**
     * 获取元素个数
     * @return
     */
    public int getSize(){
        return size;
    }

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

    /**
     * 在链表的index(0-based)位置添加新的元素e
     * 在链表中不是一个常规操作,仅仅作为练习
     * @param e
     */
    public void add(int index, E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }

        Node<E> prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node<E> node = new Node<>(e);
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    /**
     * 在链表头添加新元素
     * @param e
     */
    public void addFirst(E e){
        Node<E> node = new Node<>(e);
        node.next = dummyHead.next;
        dummyHead.next = node;
        size++;
    }

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

    /**
     * 获取链表的index(0-based)位置的元素e
     * 在链表中不是一个常规操作,仅仅作为练习
     * @param index
     * @return
     */
    public E get(int index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Get failed. Illegal index.");
        }
        Node<E> cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.e;
    }

    /**
     * 获取链表的第一个元素
     * @return
     */
    public E getFirst(){
        return get(0);
    }

    /**
     * 获取链表的最后一个元素
     * @return
     */
    public E getLast(){
        return get(size - 1);
    }

    /**
     * 修改链表的index(0-based)位置的元素
     * 在链表中不是一个常规操作,仅仅作为练习
     * @param index
     * @param e
     */
    public void set(int index, E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Update failed. Illegal index.");
        }
        Node<E> cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.e = e;
    }

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

    /**
     * 从链表中删除index(0-based)位置的元素,返回删除的元素
     * 在链表中不是一个常规操作,仅仅作为练习
     * @param index
     * @return
     */
    public E remove(int index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Remove failed. Illegal index.");
        }
        Node<E> prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node<E> retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size -- ;
        return retNode.e;
    }

    /**
     * 从链表中删除第一个元素,返回删除的元素
     * @return
     */
    public E removeFirst(){
        return remove(0);
    }

    /**
     * 删除链表最后一个元素,返回删除的元素
     * @return
     */
    public E removeLast(){
        return remove(size - 1);
    }

    /**
     * 删除链表元素
     * @param e
     * @return
     */
    public boolean delete(E e) {
        if (isEmpty())
            throw new NoSuchElementException();

        Node<E> cur = dummyHead;
        for (int i = 0; i < size; i++) {
            if(cur.next.e.equals(e)){
                Node<E> delNode = cur.next;
                cur.next = delNode.next;
                delNode.next = null;
                size -- ;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 反转链表
     * @return
     */
    public void reverseList() {
        //定义前置节点
        Node<E> prev = null;
        //定义当前节点
        Node<E> cur = dummyHead.next;
        while(cur != null){
            //当前节点的下一节点
            Node<E> next = cur.next;
            //当前节点指向前置节点
            cur.next = prev;
            //当前节点赋值为前置节点
            prev = cur;
            //下一节点赋值为当前节点
            cur = next;
        }
        //设置反转后的链表
        dummyHead.next = prev;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LinkedList: head ");
        Node<E> cur = dummyHead.next;
        while (cur != null){
            sb.append(cur + "->");
            cur = cur.next;
        }
        sb.append("NULL tail");
        return sb.toString();
    }
}

单向链表(while循环)实现

public class LinkedList2<E> {

    private class Node<E>{
        public E e;

        public Node<E> next;

        public Node(E e){
            this.e = e;
        }

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

    private Node<E> dummyHead;

    private Integer size;

    public LinkedList2(){
        dummyHead = new Node<>(null);
        size = 0;
    }

    /**
     * 获取元素个数
     * @return
     */
    public int getSize(){
        return size;
    }

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

    /**
     * 在链表的index(0-based)位置添加新的元素e
     * 在链表中不是一个常规操作,仅仅作为练习
     * @param e
     */
    public void add(int index, E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }

        Node<E> prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node<E> node = new Node<>(e);
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    /**
     * 在链表头添加新元素
     * @param e
     */
    public void addFirst(E e){
        Node<E> node = new Node<>(e);
        node.next = dummyHead.next;
        dummyHead.next = node;
        size++;
    }

    /**
     * 在链表尾部添加新元素
     * @param e
     */
    public void addLast(E e){
        Node<E> node = new Node<>(e);
        Node<E> cur = dummyHead.next;
        if(cur == null){
            addFirst(e);
        }else{
            while (cur.next!=null){
                cur = cur.next;
            }
            cur.next = node;
            size++;
        }
    }

    /**
     * 获取链表的第一个元素
     * @return
     */
    public E getFirst(){
        Node<E> cur = dummyHead.next;
        if(cur == null){
            return null;
        }
        return cur.e;
    }

    /**
     * 获取链表的最后一个元素
     * @return
     */
    public E getLast(){
        Node<E> cur = dummyHead.next;
        if(cur == null){
            return null;
        }else {
            while (cur.next != null){
                cur = cur.next;
            }
        }
        return cur.e;
    }

    /**
     * 修改链表的index(0-based)位置的元素
     * 在链表中不是一个常规操作,仅仅作为练习
     * @param index
     * @param e
     */
    public void set(int index, E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Update failed. Illegal index.");
        }
        Node<E> cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.e = e;
    }

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

    /**
     * 从链表中删除第一个元素,返回删除的元素
     * @return
     */
    public E removeFirst(){
        if(isEmpty()){
            throw new IllegalArgumentException("Remove failed. linkedList is empty");
        }
        Node<E> prev = dummyHead;
        Node<E> retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size -- ;
        return retNode.e;
    }

    /**
     * 删除链表元素
     * @param e
     * @return
     */
    public boolean delete(E e) {
        if (isEmpty())
            throw new NoSuchElementException();

        Node<E> cur = dummyHead;
        while (cur.next != null) {
            if(cur.next.e.equals(e)){
                Node<E> delNode = cur.next;
                cur.next = delNode.next;
                delNode.next = null;
                size -- ;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 反转链表
     * @return
     */
    public void reverseList() {
        //定义前置节点
        Node<E> prev = null;
        //定义当前节点
        Node<E> cur = dummyHead.next;
        while(cur != null){
            //当前节点的下一节点
            Node<E> next = cur.next;
            //当前节点指向前置节点
            cur.next = prev;
            //当前节点赋值为前置节点
            prev = cur;
            //下一节点赋值为当前节点
            cur = next;
        }
        //设置反转后的链表
        dummyHead.next = prev;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LinkedList: head ");
        Node<E> cur = dummyHead.next;
        while (cur != null){
            sb.append(cur + "->");
            cur = cur.next;
        }
        sb.append("NULL tail");
        return sb.toString();
    }
}

双向链表实现

public class DoubleLinkedList<E> {

    private class Node<E>{
        public E e;

        public Node<E> next;

        public Node<E> prev;

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

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

    private Node<E> head;

    private Node<E> tail;

    private Integer size;

    public DoubleLinkedList(){
        size = 0;
    }

    /**
     * 获取元素个数
     * @return
     */
    public int getSize(){
        return size;
    }

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

    /**
     * 在链表头添加新元素
     * @param e
     */
    public void addFirst(E e){
        Node<E> node = head;
        Node<E> newNode = new Node<>(null, e, node);
        head = newNode;
        if(node == null){
            tail = newNode;
        }else{
            node.prev = newNode;
        }
        size++;
    }

    /**
     * 在链表尾部添加新元素
     * @param e
     */
    public void addLast(E e){
        Node<E> node = tail;
        Node<E> newNode = new Node<>(node, e, null);
        tail = newNode;
        if (node == null)
            head = newNode;
        else
            node.next = newNode;
        size++;
    }

    public void add(Integer index, E e){
        if(index < 0 || index > size - 1){
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }
        if(index == 0){
            addFirst(e);
            return;
        }
        if(index == size - 1){
            addLast(e);
            return;
        }
        Node<E> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        Node<E> prev = cur.prev;
        Node<E> newNode = new Node<>(prev, e, cur);
        cur.prev = newNode;
        prev.next = newNode;
        size++;
    }

    /**
     * 获取链表的第一个元素
     * @return
     */
    public E getFirst(){
        if (head == null)
            throw new NoSuchElementException();
        return head.e;
    }

    /**
     * 获取链表的最后一个元素
     * @return
     */
    public E getLast(){
        if (tail == null)
            throw new NoSuchElementException();
        return tail.e;
    }

    /**
     * 获取链表的index(0-based)位置的元素e
     * 在链表中不是一个常规操作,仅仅作为练习
     * @param index
     * @return
     */
    public E get(int index){
        if(index < 0 || index > size - 1){
            throw new IllegalArgumentException("Get failed. Illegal index.");
        }
        Node<E> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.e;
    }

    /**
     * 修改链表的index(0-based)位置的元素
     * 在链表中不是一个常规操作,仅仅作为练习
     * @param index
     * @param e
     */
    public void set(int index, E e){
        if(index < 0 || index > size - 1){
            throw new IllegalArgumentException("Update failed. Illegal index.");
        }
        if(index == 0){
            head.e = e;
            return;
        }
        if(index == size - 1){
            tail.e = e;
            return;
        }
        Node<E> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.e = e;
    }

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

    /**
     * 从链表中删除第一个元素,返回删除的元素
     * @return
     */
    public E removeFirst(){
        if (head == null)
            throw new NoSuchElementException();
        Node<E> delNode = head;
        if(delNode.next == null){
            head = tail = null;
        }else {
            head = delNode.next;
            head.prev = null;
            delNode.next = null;
        }
        size--;
        return delNode.e;
    }

    /**
     * 删除链表最后一个元素,返回删除的元素
     * @return
     */
    public E removeLast(){
        if (tail == null)
            throw new NoSuchElementException();
        Node<E> delNode = tail;
        if(delNode.prev == null){
            head = tail = null;
        }else {
            tail = delNode.prev;
            tail.next = null;
            delNode.prev = null;
        }
        size--;
        return delNode.e;
    }

    /**
     * 删除链表元素
     * @param e
     * @return
     */
    public boolean delete(E e) {
        if (head == null)
            throw new NoSuchElementException();

        Node<E> cur = head;
        while (cur != null) {
            if(cur.e.equals(e)){
                Node<E> prev = cur.prev;
                Node<E> next = cur.next;

                //当前节点为头结点
                if (prev == null) {
                    head = next;
                } else {
                    prev.next = next;
                    cur.prev = null;
                }
                //当前节点为尾节点
                if (next == null) {
                    tail = prev;
                } else {
                    next.prev = prev;
                    cur.next = null;
                }
                size--;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 从链表中删除index(0-based)位置的元素,返回删除的元素
     * 在链表中不是一个常规操作,仅仅作为练习
     * @param index
     * @return
     */
    public E remove(int index){
        if(index < 0 || index > size - 1){
            throw new IllegalArgumentException("Remove failed. Illegal index.");
        }
        if(index == 0){
            return removeFirst();
        }
        if(index == size - 1){
            return removeLast();
        }
        Node<E> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
        cur.next = null;
        cur.prev = null;
        size -- ;
        return cur.e;
    }

    /**
     * 反转链表
     * @return
     */
    public void reverseList() {
        //定义前置节点
        Node<E> prev = null;
        //定义当前节点
        Node<E> cur = head;
        while(cur != null){
            //当前节点的下一节点
            Node<E> next = cur.next;
            //当前节点next指向前置节点
            cur.next = prev;
            //当前节点prev指向next节点
            cur.prev = next;
            //当前节点赋值为前置节点
            prev = cur;
            //下一节点赋值为当前节点
            cur = next;
        }
        //设置反转后的链表
        head = prev;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LinkedList: head ");
        Node<E> cur = head;
        while (cur != null){
            sb.append(cur + "->");
            cur = cur.next;
        }
        sb.append("NULL tail");
        return sb.toString();
    }
}

参考: https://blog.csdn.net/weixin_39084521/article/details/89820104

https://www.pianshen.com/article/2658786689/

标签:Node,index,return,cur,next,链表,数据结构
From: https://blog.51cto.com/u_14014612/6031732

相关文章

  • 判断是否为回文链表
    /***Definitionforsingly-linkedlist.*functionListNode(val,next){*this.val=(val===undefined?0:val)*this.next=(next===undefined......
  • 合并两个有序链表
    /***Definitionforsingly-linkedlist.*functionListNode(val,next){*this.val=(val===undefined?0:val)*this.next=(next===undefined......
  • 删除链表的倒数第N个节点
    /***Definitionforsingly-linkedlist.*functionListNode(val,next){*this.val=(val===undefined?0:val)*this.next=(next===undefined......
  • [数据结构] 根据前中后序遍历中的两种构造二叉树
    前中后序遍历前中后序遍历的特点前序遍历前序遍历顺序:根节点->左子树->右子树前序遍历结果:[根节点,[左子树前序遍历结果],[右子树前序遍历结果]]假如把前序遍历结果......
  • Python-数据结构
    数据结构:数据是一个抽象的概念,将其进行分类后得到程序设计语言中的基本类型。如int/float/char等。数据元素之间不是独立的,存在特点的关系,这些关系便是结构。数据结构指数......
  • 代码随想录(2)-链表
    题单203.移除链表元素链表节点对象publicclassListNode{//结点的值intval;//下一个结点ListNodenext;//节点的构造函数(无参)......
  • 网络协议中的数据结构
    我对Context和Handler是最迷惑的,什么玩意儿,用他就实现通信啦??没有直观理解,不知道到底扮演一个什么角色。1、Context上下文可以从里面获取session等对象,是个容器。准确......
  • BM2 链表内指定区间反转
    https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tqId=654&ru=%2Fpractice%2F1291064f4d5d4bdeaefbf0dd47d78541&qru=%2Fta%2Fformat-top10......
  • 剑指 Offer 06. 从尾到头打印链表
    题目:思路:【1】本质上,递归,辅助栈都是可以实现的方法,但是相比于递归,如果能用循环解决的话我更喜欢循环,因为递归也是需要消耗内存空间的,而且本质上其实只需要知道链表大小......
  • 双向链表
    双向链表单链表查找某结点的后继结点的执行时间为O(1);单链表查找某结点的后继结点的执行时间为O(n)在单链表的每个结点里再增加一个指向其直接前驱的指针域prior,这样链......