Java实现链表数据结构的方法

2024-10-20 10:52:14

什么是链表？

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。
每一个链表都包含多个节点，节点又包含两个部分，一个是数据域（储存节点含有的信息），一个是引用域（储存下一个节点或者上一个节点的地址）。

链表的理解示意图:

链表的特点是什么？

获取数据麻烦，需要遍历查找，比数组慢
方便插入、删除

简单的链表的实现原理

创建一个节点类，其中节点类包含两个部分，第一个是数据域（你到时候要往节点里面储存的信息），第二个是引用域（相当于指针，单向链表有一个指针，指向下一个节点；双向链表有两个指针，分别指向下一个和上一个节点）

创建一个链表类，其中链表类包含三个属性：头结点、尾节点和大小，方法包含添加、删除、插入等等方法。通用节点抽象类

package com.lineardatastructure.linked;
/**
 * @author huanmin
 * @param <T>
 */
/**
 * 自定义链表接口定义
 **/
public abstract class LinkedAbs<T> implements Iterable<T> {
    //列表长度
    public int size = 0;
    //当前节点
    public Node head;
    //尾节点
    public Node end;
    //节点
    protected class Node {
        Node previous = null;//上一个结点
        Node next = null;//下一个结点
        T data;//结点数据
        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
        public Node(Node next, Node previous) {
            this.next = next;
            this.previous = previous;
        }
        public Node(T data, Node next, Node previous) {
            this.next = next;
            this.previous = previous;
        }
        public Node(T data) {
            this.data = data;
        }
    }
    /**
     * 判断链表是否有环：
     * 有环返回环的入口节点,没有返回null
     * 设置快指针和慢指针，慢指针每次走一步，快指针每次走两步
     * 当快指针与慢指针相等时，就说明该链表有环,并且这个节点就是环的入口
     */
    public Node isRinged(){
        if(head == null){
            return null;
        }
          Node slow = head;
        Node fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                return fast;
            }
        }
        return null;
    }
    // 获取链表头元素
    public T getFrom() {
        return head.data;
    }
    //获取链表结尾元素
    public T getEnd() {
        return end.data;
    }
    //获取链表中元素个数
    public int getSize() {
        return size;
    }
    /**
     * 判断链表中是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }
    /**
     * 销毁链表
     */
    public void stackDestroy() {
        head = null;
        size = 0;
        end=null;
    }
    //寻找单链表的中间结点：
    public  abstract T findMiddle();
    /**
     * 元素反转
     */
    public abstract void reserveLink();
    /**
     * 获取指定元素
     *
     * @param index
     */
    public abstract T get(int index);
    /**
     * 向链表中添加元素
     *
     * @param e
     */
    public abstract void addFirst(T e);
    public abstract void addlast(T e);
    public abstract void add(T e);
    /**
     * 从链表中删除元素
     */
    public abstract boolean remove(T obj);
    public abstract boolean remove(int index);
    public abstract boolean removeFirst();
    public abstract boolean removeLast();
}

实现单向链表

package com.lineardatastructure.linked;
import java.util.Iterator;
/**
 * @author huanmin
 * @param <T>
 */
// 单向链表
public class OneWayLinked<T> extends LinkedAbs<T> {
    @Override
    public void reserveLink() {
        Node curNode = head;//头结点
        Node preNode = null;//前一个结点
        while(curNode != null){
            Node nextNode = curNode.next;//保留下一个结点
            curNode.next = preNode;//指针反转
            preNode = curNode;//前结点后移
            curNode = nextNode;//当前结点后移
        }
        head = preNode;
    }
    /**
     * 寻找单链表的中间结点：
     * 方法一、先求出链表的长度，再遍历1/2链表长度，寻找出链表的中间结点
     * 方法二、：
     * 用两个指针遍历链表，一个快指针、一个慢指针，
     * 快指针每次向前移动2个结点，慢指针一次向前移动一个结点，
     * 当快指针移动到链表的末尾，慢指针所在的位置即为中间结点所在的位置
     */
    @Override
    public T findMiddle() {
        Node slowPoint = head;
        Node quickPoint = head;
        //quickPoint.next == null是链表结点个数为奇数时，快指针已经走到最后了
        //quickPoint.next.next == null是链表结点数为偶数时，快指针已经走到倒数第二个结点了
        //链表结点个数为奇数时,返回的是中间结点；链表结点个数为偶数时，返回的是中间两个结点中的前一个
        while (quickPoint.next != null && quickPoint.next.next != null) {
            slowPoint = slowPoint.next;
            quickPoint = quickPoint.next.next;
        }
        return slowPoint.data;
    }
    /**
     * 查询指定下标数据
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        if(size<0 || index>size){//待查询结点不存在
            return null;
        }
        if(index == 0){//查询头结点
            return head.data;
        }
        Node curNode =head;
        int i = 0;
        while (curNode != null) {
            if(i==index){//寻找到待查询结点
                return  curNode.data;
            }
            //当先结点和前结点同时向后移
            curNode = curNode.next;
            i++;
        }
        return null;
    }
    @Override
    public void addFirst(T e) {
    }
    @Override
    public void addlast(T e) {
    }
    /**
     * 链表添加结点:
     * 找到链表的末尾结点，把新添加的数据作为末尾结点的后续结点
     *
     * @param data
     */
    @Override
    public void add(T data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            end=head;//添加尾节点
            size++;
            return;
        }
        Node temp = end;
        temp.next = newNode;
        end=newNode;//修改尾节点
        size++;
    }
    /**
     * 链表删除结点:
     * 把要删除结点的前结点指向要删除结点的后结点，即直接跳过待删除结点
     * @param obj
     * @return
     */
    @Override
    public boolean remove(T obj) {
        if (head.data.equals(obj)) {//删除头结点
            head = head.next;
            size=0;
            return true;
        }
        Node preNode = head;
        Node curNode = preNode.next;
        while (curNode != null) {
            if (curNode.data.equals(obj)) {//寻找到待删除结点
                preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点
                size--;
                return true;
            }
            //当先结点和前结点同时向后移
            preNode = preNode.next;
            curNode = curNode.next;
        }
        return  false;
    }
    @Override
    public boolean remove(int index) {
        if(size<0 || index>size){//待删除结点不存在
            return false;
        }
        if(index == 0){//删除头结点
            head = head.next;
            return true;
        }
        Node preNode = head;
        Node curNode =head.next;
        int i =1; //从第2个值开始
        while(preNode.next != null){
            if(i==index){//寻找到待删除结点
                preNode.next= curNode.next;//待删除结点的前结点指向待删除结点的后结点
                return true;
            }
            //当先结点和前结点同时向后移
            preNode=curNode;
            curNode = curNode.next;
            i++;
        }
        return false;
    }
    @Override
    public boolean removeFirst() {
        return false;
    }
    @Override
    public boolean removeLast() {
        return false;
    }
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node cursor = head;
            T data;
            @Override
            public boolean hasNext() {
                if (cursor != null) {
                    data = cursor.data;
                    cursor = cursor.next;
                    return true;
                }
                return false;
            }
            @Override
            public T next() {
                return data;
            }
            @Override
            public void remove() {
                OneWayLinked.this.remove(data);
            }
        };
    }
}

单向环形链表

它和单链表的区别在于结尾点的指针域不是指向null，而是指向头结点，形成首尾相连的环。这种首尾相连的单链表称为单向循环链表。循环链表可以从任意一个结点出发，访问到链表中的全部结点。

单向循环链表的查找、删除和修改操作与单链表一致(这里不在赘述，可参考前面的内容)，插入操作和单链表有所不同，单向循环链表需要维持环状结构。判断单链表为空的条件是head.next == null，而判断单向循环链表为空的条件为head.next == head。

package com.lineardatastructure.linked;
import java.util.Iterator;
/**
 * @param <T>
 * @author huanmin
 */
// 单向循环链表
public class OneLoopWayLinked<T> extends LinkedAbs<T> {
    @Override
    public void reserveLink() {
        Object[] ts = new Object[size];
        int i = size - 1;
        for (T t : this) {
            ts[i] = t;
            i--;
        }
        Node node = head;
        node.data = (T) ts[0];
        for (int i1 = 1; i1 < ts.length; i1++) {
            Node node1 = new Node((T) ts[i1]);
            node.next = node1;
            node = node1;
            end= node1;
        }
        //调整位置
        end.next=head;
    }
    /**
     * 寻找单链表的中间结点：
     * 方法一、先求出链表的长度，再遍历1/2链表长度，寻找出链表的中间结点
     * 方法二、：
     * 用两个指针遍历链表，一个快指针、一个慢指针，
     * 快指针每次向前移动2个结点，慢指针一次向前移动一个结点，
     * 当快指针移动到链表的末尾，慢指针所在的位置即为中间结点所在的位置
     */
    @Override
    public T findMiddle() {
        Node slowPoint = head;
        Node quickPoint = head;
        //quickPoint.next == null是链表结点个数为奇数时，快指针已经走到最后了
        //quickPoint.next.next == null是链表结点数为偶数时，快指针已经走到倒数第二个结点了
        //链表结点个数为奇数时,返回的是中间结点；链表结点个数为偶数时，返回的是中间两个结点中的前一个
        while (quickPoint.next != head && quickPoint.next.next != head) {
            slowPoint = slowPoint.next;
            quickPoint = quickPoint.next.next;
        }
        return slowPoint.data;
    }
    /**
     * 查询指定下标数据
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        if (size < 0 || index > size) {//待查询结点不存在
            return null;
        }
        if (index == 0) {//查询头结点
            return head.data;
        }
        Node curNode = head.next;
        int i = 1;
        while (curNode != head) {
            if (i == index) {//寻找到待查询结点
                return curNode.data;
            }
            //当先结点和前结点同时向后移
            curNode = curNode.next;
            i++;
        }
        return null;
    }
    @Override
    public void addFirst(T e) {
    }
    @Override
    public void addlast(T e) {
    }
    /**
     * 链表添加结点:
     * 找到链表的末尾结点，把新添加的数据作为末尾结点的后续结点
     *
     * @param data
     */
    @Override
    public void add(T data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            head.next = head; //环型
            end = head;//添加尾节点
            size++;
            return;
        }
        Node temp = end;
        //一直遍历到最后
        temp.next = newNode;
        newNode.next = head;//环型
        end = newNode;//修改尾节点
        size++;
    }
    /**
     * 链表删除结点:
     * 把要删除结点的前结点指向要删除结点的后结点，即直接跳过待删除结点
     *
     * @param obj
     * @return
     */
    @Override
    public boolean remove(T obj) {
        if (head.data.equals(obj)) {//删除头结点
            head = head.next;
            end.next=head;//调整环
            size--;
            return true;
        }
        Node preNode = head;
        Node curNode = preNode.next;
        while (curNode != head) {
            if (curNode.data.equals(obj)) {//寻找到待删除结点
                preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点
                size--;
                return true;
            }
            //当先结点和前结点同时向后移
            preNode = preNode.next;
            curNode = curNode.next;
        }
        return false;
    }
    @Override
    public boolean remove(int index) {
        if (size < 0 || index > size) {//待删除结点不存在
            return false;
        }
        if (index == 0) {//删除头结点
            head = head.next;
            end.next=head;//调整环
            size--;
            return true;
        }
        Node preNode = head;
        Node curNode = head.next;
        int i = 1; //从第2个值开始
        while (preNode.next != head) {
            if (i == index) {//寻找到待删除结点
                preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点
                return true;
            }
            //当先结点和前结点同时向后移
            preNode = curNode;
            curNode = curNode.next;
            i++;
        }
        size--;
        return false;
    }
    @Override
    public boolean removeFirst() {
        return false;
    }
    @Override
    public boolean removeLast() {
        return false;
    }
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node cursor = head;
            T data;
            @Override
            public boolean hasNext() {
                if (cursor != null&&cursor.next != head) {
                    data = cursor.data;
                    cursor = cursor.next;
                    return true;
                }
                if (cursor != null) {
                    data = cursor.data;
                    cursor = null;
                    return true;
                }
                return false;
            }
            @Override
            public T next() {
                return data;
            }
            @Override
            public void remove() {
                OneLoopWayLinked.this.remove(data);
            }
        };
    }
}

实现双向链表

package com.lineardatastructure.linked;
import java.util.Iterator;
/**
 * @author huanmin
 * @param <T>
 */
public class BothwayLinked<T> extends LinkedAbs<T> {
    /**
     *  查询指定下标数据
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        if (size < 0 || index > size) {//待查询结点不存在
            return null;
        }
        if (index == 0) {//查询头结点
            return head.data;
        }
        Node curNode = head;
        int i = 0;
        while (curNode != null) {
            if (i == index) {//寻找到待查询结点
                return curNode.data;
            }
            //当先结点和前结点同时向后移
            curNode = curNode.next;
            i++;
        }
        return null;
    }
    @Override
    public void addFirst(T e) {
        Node next = head;
        Node previous = new Node(e);
        previous.next = next;
        next.previous = previous;
        head=previous;
        size++;
    }
    @Override
    public void addlast(T e) {
        Node newNode = new Node(e);
        if (head == null) {
            head = newNode;
            size++;
            end=head;//添加尾节点
            return;
        }
        Node temp = end;
        temp.next = newNode;
        newNode.previous = temp;
        end=newNode;//修改尾节点
        size++;
    }
    @Override
    public void add(T e) {
        addlast(e);
    }
    @Override
    public boolean remove(T obj) {
        if (removeHead()) {
            return true;
        }
        Node curNode = head;
        while (curNode != null) {
            //寻找到待删除结点
            if (curNode.data.equals(obj)) {
                //将删除的节点后节点,覆盖删除的节点,然后将父节点指向被删除元素的父节点
                Node previous = curNode.previous;
                Node next = curNode.next;
                if (next == null) {
                    //删除的是最后节点,那么就把他上一个节点的下一个节点删除
                    previous.next=null;
                } else if (previous==null) {
                    //删除的是头节点的话,那么就不管父节点了
                    head=head.next;
                    head.previous=null;
                } else {
                    next.previous = previous;
                    previous.next = next;
                }
                size--;
                return true;
            }
            //当先结点向后移
            curNode = curNode.next;
        }
        return false;
    }
    @Override
    public boolean remove(int index) {
        if (index<0 ||index >= size) {//待删除结点不存在
            return false;
        }
        if (removeHead()) {
            return true;
        }
        Node curNode = head;
        int i = 0;
        while (curNode != null) {
            if (i == index) {//寻找到待删除结点
                //将删除的节点后节点,覆盖删除的节点,然后将父节点指向被删除元素的父节点
                Node previous = curNode.previous;
                Node next = curNode.next;
                if (next == null) {
                    //删除的是最后节点,那么就把他上一个节点的下一个节点删除
                    previous.next=null;
                } else if (previous==null) {
                    //删除的是头节点的话,那么就不管父节点了
                    head=head.next;
                    head.previous=null;
                } else {
                    next.previous = previous;
                    previous.next = next;
                }
                size--;
                return true;
            }
            //当先结点向后移
            curNode = curNode.next;
            i++;
        }
        return false;
    }
    @Override
    public boolean removeFirst() {
        if (removeHead()) {
            return true;
        }
        Node node = head.next;
        node.previous = null;
        head = node;
        size--;
        return false;
    }
    @Override
    public boolean removeLast() {
        if (removeHead()) {
            return true;
        }
        //删除尾节点
        end.previous.next=null;
        size--;
        return true;
    }
    //如果只有一个元素那么就将头删除
    public boolean removeHead() {
        if (head.next==null) {
            head=null;
            return true ;
        }
        return  false;
    }
    @Override
    public void reserveLink() {
        Object[] ts = new Object[size];
        int i = size - 1;
        for (T t : this) {
            ts[i] = t;
            i--;
        }
        Node node = head;
        node.data = (T) ts[0];
        for (int i1 = 1; i1 < ts.length; i1++) {
            Node node1 = new Node((T) ts[i1]);
            node.next = node1;
            node1.previous = node;
            node = node1;
        }
    }
    /**
     * 寻找单链表的中间结点：
     * 方法一、先求出链表的长度，再遍历1/2链表长度，寻找出链表的中间结点
     * 方法二、：
     * 用两个指针遍历链表，一个快指针、一个慢指针，
     * 快指针每次向前移动2个结点，慢指针一次向前移动一个结点，
     * 当快指针移动到链表的末尾，慢指针所在的位置即为中间结点所在的位置
     */
    @Override
    public T findMiddle() {
        Node slowPoint = head;
        Node quickPoint = head;
        //quickPoint.next == null是链表结点个数为奇数时，快指针已经走到最后了
        //quickPoint.next.next == null是链表结点数为偶数时，快指针已经走到倒数第二个结点了
        //链表结点个数为奇数时,返回的是中间结点；链表结点个数为偶数时，返回的是中间两个结点中的前一个
        while (quickPoint.next != null && quickPoint.next.next != null) {
            slowPoint = slowPoint.next;
            quickPoint = quickPoint.next.next;
        }
        return slowPoint.data;
    }
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node cursor = head;
            T data;
            @Override
            public boolean hasNext() {
                if (cursor != null) {
                    data = cursor.data;
                    cursor = cursor.next;
                    return true;
                }
                return false;
            }
            @Override
            public T next() {
                return data;
            }
            @Override
            public void remove() {
                BothwayLinked.this.remove(data);
            }
        };
    }
}

双向循环链表

相比单链表，双向循环链表是一个更加复杂的结构。因为双向循环链表的节点不仅包含指向下一个节点的指针(next)，还包含指向前一个节点的指针(prev)。
在双向循环链表中，可见的不只有头指针head，还有尾节点end。这是和单链表的区别。
双向循环链表的头指针head的前一个节点指向end，尾节点end的后一个节点指向head。

注意: 双向循环链表,实现反查询特别容易只需要反过来遍历一遍就行

package com.lineardatastructure.linked;
import org.w3c.dom.Node;
import java.util.Iterator;
/**
 * @param <T>
 * @author huanmin
 */
public class BothwayLoopLinked<T> extends LinkedAbs<T> {
    @Override
    public void reserveLink() {
        Object[] ts = new Object[size];
        int i = size - 1;
        for (T t : this) {
            ts[i] = t;
            i--;
        }
        Node node = head;
        node.data = (T) ts[0];
        for (int i1 = 1; i1 < ts.length; i1++) {
            Node node1 = new Node((T) ts[i1]);
            node.next = node1;
            node1.previous = node;
            node = node1;
            end= node1;
        }
        //调整位置
        head.previous=end;
        end.next=head;
    }
    /**
     * 寻找单链表的中间结点：
     * 方法一、先求出链表的长度，再遍历1/2链表长度，寻找出链表的中间结点
     * 方法二、：
     * 用两个指针遍历链表，一个快指针、一个慢指针，
     * 快指针每次向前移动2个结点，慢指针一次向前移动一个结点，
     * 当快指针移动到链表的末尾，慢指针所在的位置即为中间结点所在的位置
     */
    @Override
    public T findMiddle() {
        Node slowPoint = head;
        Node quickPoint = head;
        //quickPoint.next == null是链表结点个数为奇数时，快指针已经走到最后了
        //quickPoint.next.next == null是链表结点数为偶数时，快指针已经走到倒数第二个结点了
        //链表结点个数为奇数时,返回的是中间结点；链表结点个数为偶数时，返回的是中间两个结点中的前一个
        while (quickPoint.next != head && quickPoint.next.next != head) {
            slowPoint = slowPoint.next;
            quickPoint = quickPoint.next.next;
        }
        return slowPoint.data;
    }
    /**
     *  查询指定下标数据
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        if (size < 0 || index > size) {//待查询结点不存在
            return null;
        }
        if (index == 0) {//查询头结点
            return head.data;
        }
        Node curNode = head.next;
        int i = 1;
        while ( curNode!= head) {
            if (i == index) {//寻找到待查询结点
                return curNode.data;
            }
            //当先结点和前结点同时向后移
            curNode = curNode.next;
            i++;
        }
        return null;
    }
    @Override
    public void addFirst(T e) {
        Node next = head;
        Node previous = new Node(e);
        previous.previous = head.previous;
        previous.next = next;
        next.previous = previous;
        head = previous;
        end.next=previous;//修改尾节点的指向
        size++;
    }
    @Override
    public void addlast(T e) {
        Node newNode = new Node(e);
        if (head == null) {
            head = newNode;
            head.previous=head;//环型
            head.next=head; //环型
            end=head;//添加尾节点
            size++;
            return;
        }
        Node temp = end;
        temp.next = newNode;
        newNode.previous = temp;
        newNode.next = head;//给为节点添加头节点(环型)
        end=newNode;//修改尾节点
        size++;
    }
    @Override
    public void add(T e) {
        addlast(e);
    }
    @Override
    public boolean remove(T obj) {
        if (removeHead()) {
            return true;
        }
        //头部删除需要特殊处理
        if (obj == head.data) {
            Node previous = head.previous;
            head = head.next;
            head.previous = previous;
            end.next=head;
            size--;
            return true;
        }
        Node curNode = head.next;
        while (curNode != head) {
            //寻找到待删除结点
            if (curNode.data.equals(obj)) {
                //将删除的节点后节点,覆盖删除的节点,然后将父节点指向被删除元素的父节点
                Node previous = curNode.previous;
                Node next = curNode.next;
                if (next == null) {
                    //删除的是最后节点,那么就把他上一个节点的下一个节点删除
                    previous.next = null;
                } else {
                    next.previous = previous;
                    previous.next = next;
                }
                size--;
                return true;
            }
            //当先结点向后移
            curNode = curNode.next;
        }
        return false;
    }
    @Override
    public boolean remove(int index) {
        if (removeHead()) {
            return true;
        }
        if (size < 0 || index >= size) {//待删除结点不存在
            return false;
        }
        //头部删除需要特殊处理
        if (index==0) {
            Node previous = head.previous;
            head = head.next;
            head.previous = previous;
            size--;
            return true;
        }
        Node curNode = head.next;
        int i = 1;
        while (curNode != null) {
            if (i == index) {//寻找到待删除结点
                //将删除的节点后节点,覆盖删除的节点,然后将父节点指向被删除元素的父节点
                Node previous = curNode.previous;
                Node next = curNode.next;
                if (next == null) {
                    //删除的是最后节点,那么就把他上一个节点的下一个节点给替换成头节点
                    previous.next = head;
                } else {
                    next.previous = previous;
                    previous.next = next;
                }
                size--;
                return true;
            }
            //当先结点向后移
            curNode = curNode.next;
            i++;
        }
        return false;
    }
    @Override
    public boolean removeFirst() {
        head = head.next;
        head.previous = end; //环绕
        end.next=head; //环绕
        size--;
        return false;
    }
    @Override
    public boolean removeLast() {
        //将删除结尾节点
        end.previous.next=head;
        size--;
        return true;
    }
    //如果只有一个元素那么就将头删除
    public boolean removeHead() {
        if (head.next==null) {
            head=null;
            return true ;
        }
        return  false;
    }
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node cursor = head;
            T data;
            @Override
            public boolean hasNext() {
                if (cursor != null&&cursor.next != head) {
                    data = cursor.data;
                    cursor = cursor.next;
                    return true;
                }
                if (cursor != null) {
                    data = cursor.data;
                    cursor = null;
                    return true;
                }
                return false;
            }
            @Override
            public T next() {
                return data;
            }
            @Override
            public void remove() {
                BothwayLoopLinked.this.remove(data);
            }
        };
    }
}

到此这篇关于Java实现链表数据结构的文章就介绍到这了,更多相关Java链表数据结构内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

Java 数据结构之删除链表中重复的结点

目录解析一:(不提倡) 解析二:(正解) 核心考点:链表操作,临界条件检查,特殊情况处理在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针. 解析一:(不提倡) 解决该问题较简单,且在写代码时不易出错的做法如下: 遍历一遍链表,记录重复结点的结点值. 再遍历一遍链表,逐个删除重复结点. 动图演示: 该方法需要遍历两遍链表,且需要开辟额外的内存空间存储重复结点的结点值,所以一般不提倡. /* struct ListNode { int val; st
Java实现单链表的操作

本文实例为大家分享了Java实现单链表的基本操作,供大家参考,具体内容如下顺序表:物理上逻辑上都连续:链表:物理上不一定连续,逻辑上一定连续的. 链表的概念及结构概念:连表示一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是用过链表中的引用链接次序实现的. 8种链表结构: 单项.双向带头.不带头循环.非循环主要的三种链表: 无头单项非循环链表.带头循环单链表.不带头双向循环链表代码实现 1. 接口定义 package com.github.linked.Impl; publ
Java数据结构与算法学习之循环链表

目录存储结构示意图初始化循环链表循环链表的插入首位置代码实现其他位置代码实现(总) 循环链表的删除 1.操作的为第一个元素 2.操作元素不为第一个元素代码实现(总) 循环链表的常见操作存储结构示意图优点 : 能够通过任意结点遍历整个链表结构初始化循环链表 1.循环链表的结点 typedef struct CircularNode { ElementType date; //数据域 struct CircularNode* next; //指向下一个结点的指针域 }Ci
Java数据结构与算法学习之双向链表

目录双向链表的储存结构示意图双向链表的初始化结构 1.双向链表的结点 2.双向链表的头结点 3.总代码双向链表中的指定文件插入元素 1.插入的为第一个位置 2.其他位置插入总代码双向链表的删除 1.删除第一个元素 2.删除其他位置元素总代码双向链表的储存结构示意图双向链表的初始化结构 1.双向链表的结点代码实现 //双向链表的结点,包含一个数据域,两个指针域 typedef struct DoublyNode { ElementType date; //数据域 struct
java单链表实现书籍管理系统

本文实例为大家分享了java单链表实现书籍管理系统的具体代码,供大家参考,具体内容如下书籍管理系统功能: 1).添加图书 2).删除图书 3).查看图书 4).修改书籍 5).修改排序方式 6).模糊查询 7).退出程序代码实现: Book类 package com.bookmanagement.book; public class Book {//书类 public String no; public String name; public int price; public String
Java面试题-实现复杂链表的复制代码分享

阿里终面在线编程题,写出来与大家分享一下有一个单向链表,每个节点都包含一个random指针,指向本链表中的某个节点或者为空,写一个深度拷贝函数,拷贝整个链表,包括random指针.尽可能考虑可能的异常情况. 算法如下: /* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.labe
Java实现无头双向链表操作

本文实例为大家分享了Java实现无头双向链表的具体代码,供大家参考,具体内容如下无头双向链表的结构: 代码分析节点结构 class Node { private int data; private Node next; private Node prev; public Node(int data) { this.data = data; this.prev = null; this.next = null;
Java复杂链表的复制详解

目录 1.题目 2.解法 2.1 拼接+拆分 3.代码 1.题目请实现 copyRandomList 函数,复制一个复杂链表.在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null. 题目来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof 2.解法 2.1 拼接+拆分首先我们逐个将节点复制并且和原来的链表连起
带你了解Java数据结构和算法之链表

目录 1.链表(Linked List) 2.单向链表(Single-Linked List) ①.单向链表的具体实现 ②.用单向链表实现栈 4.双端链表 ①.双端链表的具体实现 ②.用双端链表实现队列 5.抽象数据类型(ADT) 6.有序链表 7.有序链表和无序数组组合排序 8.双向链表 9.总结前面博客我们在讲解数组中,知道数组作为数据存储结构有一定的缺陷.在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且数组在创建后,其大小是固定了,设置的过大会
Java实现链表数据结构的方法

什么是链表? 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接次序实现的.每一个链表都包含多个节点,节点又包含两个部分,一个是数据域(储存节点含有的信息),一个是引用域(储存下一个节点或者上一个节点的地址). 链表的理解示意图: 链表的特点是什么? 获取数据麻烦,需要遍历查找,比数组慢方便插入.删除简单的链表的实现原理创建一个节点类,其中节点类包含两个部分,第一个是数据域(你到时候要往节点里面储存的信息),第二个是引用域(相当于指针,单向链表有一个指
Java 单链表数据结构的增删改查教程

我就废话不多说了,大家还是直接看代码吧~ package 链表; /** * *1)单链表的插入.删除.查找操作: * 2)链表中存储的是int类型的数据: **/ public class SinglyLinkedList { private Node head = null; //查找操作 public Node findByValue(int value){ Node p = head; //从链表头部开始查找 while(p.next != null && p.data != va
Java链表数据结构及其简单使用方法解析

目录认识链表结构单向链表双向链表加深对链表结构的理解实现单向和双向链表的反转实现把链表中给定的值都删除小结认识链表结构单向链表单链表在内存中的表示: 可以看到,一个链表的节点包含数据域和指向下一个节点的引用,链表最后一个节点指向null(空区域). 我们可以根据这一定义,用Java语言表示一下单向链表的结构: public class Node { public int value; public Node next; public Node(int value) { thi
Java基于链表实现栈的方法详解

本文实例讲述了Java基于链表实现栈的方法.分享给大家供大家参考,具体如下: 在上几小节中我们实现了基本的链表结构,并在上一节的底部给出了有关链表的源码,此处在贴一次吧,猛戳在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加.删除.查找操作,时间复杂度均为O(1),基于链表的这几个优势,我们在此基础上实现栈. 前言,在写本小节之前,我们已经实现了一个基于静态数组的栈,转到查看.此处我们实现基于链表的栈. 1.链表类拷贝到Stack 包下: 在实现基于静态数组的栈的时候,我们已经新建了
Java实现链表中元素的获取、查询和修改方法详解

本文实例讲述了Java实现链表中元素的获取.查询和修改方法.分享给大家供大家参考,具体如下: 本节是在上一小节Java链表中添加元素的基础上继续完善我们的链表相关方法的编写,在本节中我们着重对如何获取链表中元素.查询元素以及修改元素进行学习. 一.获取元素 1.关于获取链表中元素的方法的分析由于我们使用了虚拟头结点,而我们每次都需要从第一个真实节点开始,因此需要首先得到虚拟头结点的下一个节点是谁,然后在此基础上进行遍历工作,相关代码如下: //获取链表的第index(0-based)个位置的元
java 中链表的定义与使用方法

java 中链表的定义与使用方法 Java实现链表主要依靠引用传递,引用可以理解为地址,链表的遍历多使用递归,这里我存在一个疑问同一个类的不同对象的的相同方法的方法内调用算不算递归. 这里我写的是单向链表; 实例代码: package com.example.java; public class MyLink { public static void main(String [] args){ Link l=new Link(); mytype[] la; mytype dsome=new my
Java 精炼解读数据结构的链表的概念与实现

目录前言: 一.什么是链表链表的概念链表的结构链表如何存储数据链表的实现穷举法创建链表打印链表查找是否包含关键字key是否在单链表当中得到单链表的长度: 头插法尾插法任意位置插入,第一个数据节点为0号下标删除第一次出现关键字为key的节点删除所有值为key的节点总结: 前言: 顺序表的问题及思考 1. 顺序表中间/头部的插入删除,时间复杂度为O(N) 2. 增容需要申请新空间,拷贝数据,释放旧空间.会有不小的消耗. 3. 增容一般是呈2倍的增长,势必会有一定的空
java实现单链表倒转的方法

java中有关单链表反转的方法有很多种,这里记录一种并附上详细步骤: 代码如下 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode reverseList(Li
Java中ArrayList的removeAll方法详解

本文介绍的是关于Java中ArrayList的removeAll方法的相关内容,分享出来供大家参考学习,下面来一起看看详细的介绍: 在开发过程中,遇到一个情况,就是从所有骑手Id中过滤没有标签的骑手Id(直接查询没有标签的骑手不容易实现), List<Integer> allRiderIdList = new ArrayList(); // 所有的骑手,大致有23W数据 List<Integer> hasAnyTagRiderId = new ArrayList(); // 有标签
浅谈Java中常用数据结构的实现类 Collection和Map

线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构.这些类均在java.util包中.本文试图通过简单的描述,向读者阐述各个类的作用以及如何正确使用这些类. Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ├Hashtable ├HashMap └WeakHashMap Collection接口 Collection是最基本的集合接口,一个C