数据结构-链表的增删改查底层实现

朱雀 2022-05-25 09:40 249阅读 0赞

**链表的底层代码实现–增删改查**  
代码实现如下：

package cn.dataStructures.Stack;
    public class LinkedListDemo<E> {
        //创建内部类
        private class Note{
            public E e;
            public Note next;
            //构造方法
            public Note(E e,Note next){
                this.e=e;
                this.next=next;
            }
            public Note(E e){
                this(e,null);
            }
            public Note(){
                this(null,null);
            }
            public String toString(){
                return e.toString();
            } 
        }
        private Note dummyHeard;
        public int size;
        public LinkedListDemo(){
            dummyHeard=new Note(null,null);
            size=0;
        }
        public int getSize(){
            return size;
        }
        public boolean isEmpty(){
            return size==0;
        }
    
        //给链表任意索引位置添加元素
    
    // public void add(int index,E e){ 
    // Note prev=dummyHeard;
    // if(index<0||index>size){ 
    // throw new IllegalArgumentException("索引不合法！");
    // }
    // for(int i=0;i<index;i++){ 
    // prev=prev.next;
    // }
    // Note note=new Note(e);
    // note.next=prev.next;
    // prev.next=note;
    // size++;
    // }
        //*************
        public void add(int index,E e){
            if(index<0||index>size){
                throw new IllegalArgumentException("添加失败，不合法！");
            }   
                Note prev=dummyHeard;
                for(int i=0;i<index;i++){
                    prev=prev.next;
                }
                Note note=new Note(e);
                note.next=prev.next;
                prev.next=note;  
                size++; 
        }
        //给链表的头部添加元素
        public void addFirst(E e){
            add(0,e);
        }
        //给链表的尾部添加元素
        public void addLast(E e){
            add(size-1,e);
        }
        //获取链表的元素
        public E get(int index){
            Note cur=dummyHeard.next;
            if(index<0||index>size){
                throw new IllegalArgumentException("索引不合法！");
            }
            for(int i=0;i<index;i++){
                cur=cur.next;
            }
            return cur.e;
        }
        //获取链表的头元素
        public E getFirst(){
            return get(0);
        }
        //获取链表的头元素
        public E getLast(){
            return get(size-1);
        }
        //修改链表的元素
        public void set(int index,E e){
            Note cur=dummyHeard.next;
            if(index<0||index>size){
                throw new IllegalArgumentException("索引不合法！");
            }
            for(int i=0;i<index;i++){
                cur=cur.next;
            }
             cur.e=e;
        }
        //判断链表中是否含有指定的元素
        public boolean contains(E e){
            Note cur=dummyHeard.next;
    // for(int i=0;i<size;i++){ 
    // cur=cur.next;
    // if(cur.e.equals(e)){ 
    // return true;
    // }
    // }
            while(cur!=null){
                if(cur.e.equals(e)){
                    return true;
                }
                cur=cur.next;
            }
            return false;
        }
        //删除
        public E remove(int index){
            Note prev=dummyHeard;
            if(index<0||index>size){
                throw new IllegalArgumentException("索引不合法！");
            }
            for(int i=0;i<index;i++){
                prev=prev.next;
            }
            Note remNote=prev.next;
            prev.next=remNote.next;
            remNote.next=null;
            size--;
            return remNote.e;
        }
        //删除第一个元素
        public E removeFirst(){
            return remove(0);
        }
        //删除最后一个元素
        public E removeLast(){
            return remove(size-1);
        }
        public String toString(){
            StringBuilder res=new StringBuilder();
            Note cur=dummyHeard.next;
            while(cur!=null){
                res.append(cur+"->");
                cur=cur.next;
            }
            res.append("Null");
            return res.toString();
        }
    }

**测试代码：**

public class Test {
        public static void main(String[] args) {
            LinkedListDemo<Integer> test=new LinkedListDemo<>();
            for(int i=0;i<5;i++){
                test.addFirst(i);
                System.out.println(test);
    
            }
            test.add(2, 888);
            System.out.println(test);
            test.addLast(9999);
            System.out.println(test);
            test.get(3);
            test.remove(2);
            System.out.println(test);
        }
    }

结果如图所示：![这里写图片描述][70]

[70]: /images/20220525/5c728cf1ba6f427996e06e6be0aff266.png