java实现数据结构04.01（链表详解代码之自定义链表）

柔光的暖阳◎ 2023-06-22 13:36 49阅读 0赞

自定义链表

/**
     * @description: 自定义链表
     * @author: liangrui
     * @create: 2019-12-16 10:02
     **/
    public class LinkedList<E> {
    
        /**
         * 私有节点类
         */
        private class Node{
            public E e;
            public Node next;
    
            public Node(E e,Node next){
                this.e=e;
                this.next=next;
            }
    
            public Node(E e){
                this(e,null);
            }
    
            public Node(){
                this(null,null);
            }
    
            @Override
            public String toString() {
                return e.toString();
            }
        }
    
        //虚拟头节点，位于头节点前一个位置
        private Node dummyHead;
        //元素个数
        private int size;
    
        //无参构造函数
        public LinkedList(){
            //初始为空
            dummyHead=new Node(null,null);
            //初始为0
            size=0;
        }
    
        /**
         * 获取链表元素个数
         * @return 元素个数
         */
        public int getSize(){
            return size;
        }
    
        /**
         * 链表是否为空
         * @return 如果size==0，则链表为空返回true，否则返回false
         */
        public boolean isEmpty(){
            return size==0;
        }
    
        /**
         * 向链表任意位置添加元素
         * @param index 添加的位置
         * @param e 添加的元素
         */
        public void add(int index,E e){
            //非法索引
            if (index<0||index>size){
                throw new IllegalArgumentException("Add failed,illegal index.");
            }
            Node prev=dummyHead;
            //遍历从而获取插入位置的前一个结点
            for (int i = 0; i < index; i++) {
                prev=prev.next;
            }
            //添加元素
            prev.next=new Node(e,prev.next);
            //个数+1
            size++;
        }
    
        /**
         * 在链表首添加元素
         * @param e 添加的元素
         */
        public void addFirst(E e){
            add(0,e);
        }
    
        /**
         * 在链表尾添加元素
         * @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("Get failed,illegal index.");
            }
    
            //与添加元素不一样，因为要获取指定位置元素，添加则是获取指定位置的前一个元素
            Node 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);
        }
    
        /**
         * 修改指定位置元素
         * @param index 指定的位置
         * @param e 修改后的元素
         */
        public void set(int index,E e){
            if (index<0||index>=size){
                throw new IllegalArgumentException("Set failed,illegal index.");
            }
            Node cur=dummyHead.next;
            for (int i = 0; i < index; i++) {
                cur=cur.next;
            }
            cur.e=e;
        }
    
        /**
         * 判断链表中是否含有指定元素
         * @param e 指定的元素
         * @return 如果有返回true，否则返回false
         */
        public boolean contains(E e){
            Node cur=dummyHead.next;
            for (int i = 0; i < size; i++) {
                if (cur.e.equals(e)){
                    return true;
                }
                cur=cur.next;
            }
            return false;
        }
    
        @Override
        public String toString() {
            StringBuilder res=new StringBuilder();
            res.append("LinkedList:");
            Node cur=dummyHead.next;
            /*
            for (int i = 0; i < size; i++)与while (cur!=null)一样
             */
            while (cur!=null){
                res.append(cur+"->");
                cur=cur.next;
            }
            res.append("null");
            return res.toString();
        }
    
        /**
         * 根据索引删除元素
         * @param index
         * @return
         */
        public E removeByIndex(int index){
            if (index<0||index>=size){
                throw new IllegalArgumentException("Remove failed,illegal index.");
            }
    
            Node prev=dummyHead;
            for (int i = 0; i < index; i++) {
                prev=prev.next;
            }
    
            //要被移除的节点
            Node remNode=prev.next;
            prev.next=remNode.next;
            remNode.next=null;
            //个数-1
            size--;
    
            return remNode.e;
    
        }
    
        /**
         * 删除指定元素
         * @param e 指定的元素
         * @return 删除成功返回true，删除失败返回false
         */
        public boolean removeByElement(E e){
            Node cur=dummyHead.next;
            for (int i = 0; i < size; i++) {
                if (cur.e.equals(e)){
                    removeByIndex(i);
                    return true;
                }
                cur=cur.next;
            }
            return false;
        }
    
        /**
         * 删除链表首的元素
         * @return 返回删除的元素
         */
        public E removeFirst(){
            return removeByIndex(0);
        }
    
        /**
         * 删除链表尾的元素
         * @return 返回删除的元素
         */
        public E removeLast(){
            return removeByIndex(size-1);
        }
    
        /**
         * 移除链表中所有元素e
         * @param e 要移除的元素
         */
        public void removeElements(E e){
            Node cur=dummyHead.next;
            for (int i = 0; i < size; i++) {
                if (cur.e.equals(e)){
                    removeByIndex(i);
                }else {
                    cur=cur.next;
                }
            }
            System.out.println("Remove success.");
        }
    }

main测试：

public class Main {
    
        public static void main(String[] args) {
           LinkedList<Integer> linkedList=new LinkedList<>();
            for (int i = 0; i < 5; i++) {
                linkedList.addLast(i);
                System.out.println(linkedList);
            }
    
            System.out.println("Remove success:"+linkedList.removeByIndex(2));
    
            linkedList.add(2,666);
            System.out.println(linkedList);
    
            boolean b = linkedList.removeByElement(666);
            if (b){
                System.out.println("Remove success.");
                System.out.println(linkedList);
            }else {
                System.out.println("Remove failed,nonexistent element.");
                System.out.println(linkedList);
            }
    
        }
    }

测试结果：

> LinkedList:0->null  
> LinkedList:0->1->null  
> LinkedList:0->1->2->null  
> LinkedList:0->1->2->3->null  
> LinkedList:0->1->2->3->4->null  
> Remove success:2  
> LinkedList:0->1->666->3->4->null  
> Remove success.  
> LinkedList:0->1->3->4->null