忽悠面试官的LinkedList的底层?

拼搏现实的明天。 2023-10-07 12:21 12阅读 0赞

public Object  get(int index){
        }

没有下标的概念，通过值来获取

package com.luo.demo;
    
    /**
     * 直接封装一个LinkList集合缩小版,不完美
     * @author 戴尔
     *
     */
    public class LinkList {
        
    	
    	/**
    	 * 
    	 * 创建一个节点内部类
    	 */
    	static class Node{
        
    		Node prev;           //上一个节点
    		Node next;	        //下一个节点
    		Object elmenet;     //完美的值		
    	    public Node(Object element){
        
    	    	this.elmenet = element;
    	    }    
    	    public Node (Node prev,Node next,Object elmenet){
        	
    	    	super();
    	    	this.prev=prev;
    	    	this.next=next;
    	    	this.elmenet=elmenet;   	
    	    }	    		
    	}
    	        //没有下标  除了ArrayList
    	        private Node first;//首节点
    	        private Node last;//尾结点
    	        private int size;     //有效数位
    	/**
    	 * 添加一个元素
    	 * 
    	 */	
           public  void add(Object obj){
        
        	   Node node=new  Node(obj);//公共的共享节点
        	   if (first==null) {
        
        		   first=node;	
        		   last=node;		
    		}
       	   
        	   else{
        
    		   node.prev=last; 
    		   node.next=null;
    		   last.next=node;
    		   last=node;	
    	       }   
        	   size++;
           }
           /***
            * 
            * 根据传入的index的值获取对应的element
            * 
            * @param index
            * @return
            */
           public Object  get(int index){
        
        	   rangeCheck(index);
    //    	   //从第一个节点往下遍历,找到就ok
    //    	   Node temp=first;  //第一个节点
    //    	   for (int i = 0; i < index; i++) {  //没有下标的概念 通过传值来获取
    //    		   temp=temp.next;		
    //		}   
    //    	   Node temp=null;
    //    	   //size有效数位(size/2)   下面位移的手段提高  查询的速度
    //    	   //使用二分明显减少遍历次数 ，提高了效率
    //    	   System.out.println("次数"+size/2);
    //    	   if (index < size / 2) {
        
    //    		   temp=first;
    //    		   for (int i = 0; i < index; i++) {
        
    //				temp=temp.next;			
    //    		   }
    //    		}else{
        
    //    			temp=last;
    //    			for (int i = size-1; i > index; i--) {
        
    //    				temp=temp.prev;					
    //				}
    //    			
    //    		}
        	   Node temp=this.getNode(index);	   
        	   return temp !=null ? temp.elmenet:null;
           }
           
           /***
            * 获取节点
            * @param index
            * @return
            */
           public Node getNode(int index){
        
        	   rangeCheck(index) ;
        	   Node temp=null;
        	   System.out.println("次数"+size/2);
        	   if (index < size / 2) {
        
        		   temp=first;
        		   for (int i = 0; i < index; i++) {
        
    				temp=temp.next;			
        		   }
        		}else{
        
        			temp=last;
        			for (int i = size-1; i > index; i--) {
        
        				temp=temp.prev;					
    				}
        			
        		}   
        	   return temp;
        	   
           }
           /***
            * 根据下标	删除节点(没有下标 是给的值)
            * @param index
            */
           public   void  remove(int index){
        
        	   rangeCheck(index);
        	   Node temp=this.getNode(index);  //给到对应的节点  也就是找到了 我们要删除的那个节点
        	   if (temp!=null) {
        
    			//现在我要分别拿到  删除节点的   上一个 节点和下一个节点
        		   Node top=temp.prev;   //拿到上一个节点
        		   Node down=temp.next;  //拿到下一个节点
        		  if (top!=null) {
           //和down挂上链了
        			  top.next=down;
    				
    			}  
        		  if (down!=null) {
        
        			  down.prev=top; //和up挂上链了
        			  
    				
    			}
        		  if (index==0) {
        
        			  first=down;
        			  down.prev=null; 	
    				
    			}
        		  if (index==size-1) {
        //最后一个节点
        			  last=top;
        			  top.next=null;
    				
    			}	   
    		}
        	   size--;
        	   
        	   
        	   
           }
           /***
            * 指定位置添加接节点，没有考虑最后一个和第一个节点
            * @param index
            * @param obj
            */
           public void add(int index,Object obj){
        
        	   Node Newnode=new Node(obj);
        	   rangeCheck(index); 
        	   Node temp=this.getNode(index);  //拿到添加节点位置的那个节点	
        	   if (temp!=null) {
        
        		   Node  top=temp.prev;
        		   top.next=Newnode;
        		   Newnode.prev=top;
        		   Newnode.next=Newnode;
    			
    		}
        	   size--;
        	   
        	   
        	   
        	   
           }
           
           
           
           
           
           public  void rangeCheck(int index)  {
        
        	   if(index < 0 || index > size) {
        
        		   
        		   throw new RuntimeException("索引不正确"+ index);
        	   }
        	   
           }
           
           
           /***
            * 展示方法
            * 
            * 
            */     
           public String toString(){
        
        	   StringBuilder sb=new StringBuilder();
        	   sb.append("[");
        	   //从第一个节点遍历到最后一个节点
        	   Node temp=first;
        	   while (temp!=null) {
        
    		     sb.append(temp.elmenet+",");
    		     temp=temp.next;		
    		}    
              sb.setCharAt(sb.length() -1, ']');
              return sb.toString();
        
        	   
        	   
        	   
        	   
           }
           
    }

package com.luo.demo;
    
    public class text {
        
    	
    	public static void main(String[] args) {
        
    		LinkList list=new LinkList();
    		list.add("a");
    		list.add("b");
    		list.add("c");
    		list.add("d");
    		list.add("e");
    		list.add("f");
    		list.add("g");
    		list.add("h");
    		list.add("i");
    		list.add("o");
    		System.out.println(list);
    		
    //		//增加
    //		list.add(2, "zz");
    //		System.out.println(list);
    //		//删除
    //		System.out.println(list);
    		list.remove(2);
    	System.out.println(list);
    //		//获取
    //		Object obj=list.get(3);
    //		System.out.println(obj);
    		
    
    		
    	}
    
    }