Java 自定义链表实现

迷南。 2022-10-24 01:38 118阅读 0赞

两个方法可能存在一定的问题，毕竟每个人实现的不一样。  
两个代码的思路可以参考，会有帮助的。

我写了代码二的一部分  
对于 get 方法 Java LinkedList 默认下标从零开始

public E getNode(int index){ 
                Node get = this ;
            	for(int i = 0 ; i < index ; i++) { 
            		get = this.next ;
            	}
                return (E) get.data;
          }
        //根据索引获取数据
        @Override
        public E get(int index) { 
            if (index+1 > this.count || index < 0)//索引应该在范围内
                throw new IndexOutOfBoundsException("Index: "+ index+", Size: "+ this.count) ;
            return (E) this.root.getNode(index);
        }

## 方法一： ##

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();
            size = 0;
        }
    
        // 获取链表中的元素个数
        public int getSize(){ 
            return size;
        }
    
        // 返回链表是否为空
        public boolean isEmpty(){ 
            return size == 0;
        }
    
        // 在链表的index(0-based)位置添加新的元素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);
            size ++;
        }
    
        // 在链表头添加新的元素e
        public void addFirst(E e){ 
            add(0, e);
        }
    
        // 在链表末尾添加新的元素e
        public void addLast(E e){ 
            add(size, e);
        }
    
        // 获得链表的第index(0-based)个位置的元素
        // 在链表中不是一个常用的操作，练习用：）
        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;
        }
    
        // 获得链表的第一个元素
        public E getFirst(){ 
            return get(0);
        }
    
        // 获得链表的最后一个元素
        public E getLast(){ 
            return get(size - 1);
        }
    
        // 修改链表的第index(0-based)个位置的元素为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;
        }
    
        // 查找链表中是否有元素e
        public boolean contains(E e){ 
            Node cur = dummyHead.next;
            while(cur != null){ 
                if(cur.e.equals(e))
                    return true;
                cur = cur.next;
            }
            return false;
        }
    
        // 从链表中删除index(0-based)位置的元素, 返回删除的元素
        // 在链表中不是一个常用的操作，练习用：）
        public E remove(int index){ 
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Remove failed. Index is illegal.");
    
            Node prev = dummyHead;
            for(int i = 0 ; i < index ; i ++)
                prev = prev.next;
    
            Node retNode = prev.next;
            prev.next = retNode.next;
            retNode.next = null;
            size --;
    
            return retNode.e;
        }
    
        // 从链表中删除第一个元素, 返回删除的元素
        public E removeFirst(){ 
            return remove(0);
        }
    
        // 从链表中删除最后一个元素, 返回删除的元素
        public E removeLast(){ 
            return remove(size - 1);
        }
    
        // 从链表中删除元素e
        public void removeElement(E e){ 
    
            Node prev = dummyHead;
            while(prev.next != null){ 
                if(prev.next.e.equals(e))
                    break;
                prev = prev.next;
            }
    
            if(prev.next != null){ 
                Node delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }
        }
    
        @Override
        public String toString(){ 
            StringBuilder res = new StringBuilder();
    
            Node cur = dummyHead.next;
            while(cur != null){ 
                res.append(cur + "->");
                cur = cur.next;
            }
            res.append("NULL");
    
            return res.toString();
        }
    }

## 方法二： ##

public class LinkImpl<E> implements ILink<E> { 
        private class Node<E> { //保存节点的数据关系
            private E data; //保存节点的数据
            private Node next; //保存下一个引用
            public Node(E data){ 
                this.data=data;
            }
            //添加节点
            public void addNode(Node newNode){ //保存新的Node数据
                if (this.next==null){ 
                    this.next=newNode;
                }else
                    this.next.addNode(newNode);
            }
            //转换数组
            public void toArrayNode(){ 
                LinkImpl.this.resultData[LinkImpl.this.foot++]=this.data;
                if (this.next!=null){ //还有下一个数据
                    this.next.toArrayNode();
                }
            }
            public E getNode(int index){ 
                if (LinkImpl.this.foot ++==index)
                    return this.data;
                else
                    return (E) this.next.getNode(index);
            }
            public void setNode(int index,E data){ 
                if (LinkImpl.this.foot ++==index)
                    this.data=data;
                else
                    this.next.getNode(index);
            }
            public boolean containsNode(E data){ 
                if (data.equals(this.data))//对象比较
                    return true;
                else{ 
                    if (this.next==null)//没有后续节点了
                        return false;
                    else
                        return this.next.containsNode(data);
                }
            }
            public void removeNode(Node previous,E data){ 
                if (data.equals(this.data)){ 
                    previous.next=this.next;//空出当前节点
                }else{ 
                    if (this.next !=null){ //有后续节点
                        this.next.removeNode(this,data);
                    }
                }
            }
        }
        //--------------Link类中的成员---------
        private Node root;//保存根节点
        private int count;//记录链表长度
        private int foot;//记录数组脚标
        private Object[] resultData;//返回数组
        //-----添加元素的方法----------
        @Override
        public void add(E e) { 
            if (e==null){ //空数据直接返回
                return;
            }
            Node newNode = new Node(e);//创建一个新节点
            if (this.root==null)//没有根节点
                this.root = newNode;//第一个节点作为根节点
            else { 
                this.root.addNode(newNode);
            }
            this.count++;//链表长度加1
        }
        //------遍历链表
    // @Override
    // public void print() { 
    // Node root1 =root;
    // while (root1!=null){ 
    // System.out.println(root1.data);
    // root1 = root1.next;
    // }
    // }
        //----------数据增加的方法
        @Override
        public int size() { 
            return this.count;
        }
        //判断链表是否为空
        @Override
        public boolean isEmpty() { 
            return this.count==0;
        }
    
        //返回数组方法
        @Override
        public Object[] toArray() { 
            if (this.isEmpty())//没有数据
                return null;
            this.foot=0;
            this.resultData=new Object[this.count];//根据已有长度开辟数组
            this.root.toArrayNode();
            return this.resultData;
        }
    
        //根据索引获取数据
        @Override
        public E get(int index) { 
            if (index > this.count)//索引应该在范围内
                return null;
            this.foot=0;//重置索引下表
            return (E) this.root.getNode(index);
        }
    
        @Override
        public void set(int index, E data) { 
            if (index >=this.count)
                return;
            this.foot=0;//重置索引下标
            this.root.setNode(index,data);
        }
    
        @Override
        public boolean contains(E data) { 
            if (data ==null)//没有数据
                return false;
            return this.root.containsNode(data);
        }
    
        @Override
        public void remove(E data) { 
            if (this.contains(data)){ //判断数据是否存在
                if (this.root.data.equals(data)){ //根节点是要删除的节点
                    this.root=this.root.next;
                }else{ 
                    this.root.next.removeNode(this.root,data);
                }
                this.count--;
            }
        }
    
        @Override
        public void clean() { 
            this.root=null;//后续节点都为null
            this.count=0;
        }
    }

测试代码

public class Demo { 
        public static void main(String[] args) { 
            LinkImpl<String> s=new LinkImpl<>();
            System.out.println("增加之前："+s.size()+"、是否为空："+s.isEmpty());
            s.add("hello");
            s.add("world");
            System.out.println("增加之后："+s.size()+"、是否为空："+s.isEmpty());
            System.out.println("------链表中存在的数据----");
            Object[] obj = s.toArray();
            for (Object ob:obj){ 
                System.out.println(ob);
            }
            System.out.println("--------获取数据--------");
            System.out.println(s.get(0));
            System.out.println(s.get(3));
            System.out.println("--------修改数据--------");
            s.set(0,"你好");
            Object[] obj2 = s.toArray();
            for (Object ob:obj2){ 
                System.out.println(ob);
            }
            System.out.println("--------判断对象是否存在-----");
            System.out.println(s.contains("你好"));
            System.out.println(s.contains("ni"));
            System.out.println("--------删除---------");
            s.remove("你好");
            Object[] obj3 = s.toArray();
            for (Object ob:obj3){ 
                System.out.println(ob);
            }
            System.out.println("-----链表清空-----");
            s.clean();
            System.out.println(s.size());
        }
    }