美文网首页
java实现链表

java实现链表

作者: Swen_9826 | 来源:发表于2018-11-19 10:49 被阅读6次

    链表各个操作中,数据的删除比较特殊,其中具体操作如图所示:


    链表删除操作

    java实现动态链表代码:

    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;
            }
    
            @SuppressWarnings("unused")
            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);
        }
        // 查找链表中是否有元素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. Illegal index.");
            }
            Node prev = dummyHead;
            
            for(int i=0;i<index;i++){
                prev = prev.next;
            }
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size--;
            return delNode.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;
                size --;
            }
        }
        
        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
            for(Node cur = dummyHead.next ; cur != null ; cur = cur.next)
                res.append(cur + "->");
            res.append("NULL");
    
            return res.toString();
        }
    }
    

    具体的测试代码:

    public static void main(String args[]){
            
            LinkedList<Integer> arrayList = new LinkedList<Integer>();
            
            for(int i =0;i<10;i++){
                arrayList.add(i, i);
            }
            
            System.out.println(arrayList.toString());
            System.out.println(arrayList.contains(5));
            System.out.println(arrayList.get(8));
            arrayList.removeElement(3);
            System.out.println(arrayList.toString());
            System.out.println(arrayList.remove(5));
            System.out.println(arrayList.toString());
            
        }
    

    测试结果:


    测试结果

    链表的时间复杂度分析:


    添加操作 删除操作 添加操作 总结

    相关文章

      网友评论

          本文标题:java实现链表

          本文链接:https://www.haomeiwen.com/subject/anjofqtx.html