JAVA（手写）简单实现ArrayList和LinkedList

灰太狼 2022-04-18 05:16 225阅读 0赞

# JAVA（手写）简单实现ArrayList和LinkedList #

大家都知道在java学习中list类的实现类中有ArrayList 和LinkedList，其中ArrayList是使用数组实现，而LinkedList则是用链表实现的。今天就自己去用java去简单实现一下它们。

## 1.ArrayList的实现 ##

1.类必须的属性  
一个object的数组  
list的长度  
2.基本代码

`public class MyArrayList {
       private Object[] objs;//一个object数组
       private int size;//大小
       public MyArrayList() {
    	   this(10);//初始大小为10
       }
       public MyArrayList(int initCapacity) {
    	   objs=new Object[initCapacity];
       }
       public void add(Object object) {
           //size是否小于obj的长度
    	   if(size<objs.length) {
    		   objs[size]=object;
    		   size++;
    	     }
    	   else{
    		   Object[] bObjects=new Object[size*2];
    		   for(int i=0;i<objs.length;i++) {
    			   bObjects[i]=objs[i];  
    		   }
    		   objs=bObjects;
    		   objs[size]=object;
    		   size++;
    	     }
       }
       
       public static void main(String[] args) {
    	MyArrayList list=new MyArrayList(2);
        List ls=new ArrayList<Integer>();
        ls.add(1);
    	list.add("aaaa");
    	list.add("bb");
    	list.add("cccc");
    	list.add("sadasda");
    	System.out.println(list.size);
    }
    }

## 2.LinkedList的实现 ##

1.创建node类

package com.list.test;
    
    public class Node {
        Node pre;//上一个节点
       Object obj;//当前数据
       Node next;//下一个节点
    public Node(Node pre, Object obj, Node next) {
    	super();
    	this.pre = pre;
    	this.obj = obj;
    	this.next = next;
    }
    public Node() {
    	
    }
    public Node getPre() {
    	return pre;
    }
    public void setPre(Node pre) {
    	this.pre = pre;
    }
    public Object getObj() {
    	return obj;
    }
    public void setObj(Object obj) {
    	this.obj = obj;
    }
    public Node getNext() {
    	return next;
    }
    public void setNext(Node next) {
    	this.next = next;
    }
    
    }

2.实现LinkedList类

package com.list.test;
    
    import org.omg.IOP.CodecPackage.InvalidTypeForEncodingHelper;
    
    public class MyLinkedList {
      private Node first;
      private Node last;
      private int size;
      public void add(Object o) {
    	  Node n=new Node();
    	  if(first==null) {
    		  n.setPre(null);
    		  n.setObj(o);
    		  n.setNext(null);
    		  first=last=n;		  
    	  }
    	  else {  
    		  n.setPre(last);
    		  n.setObj(o);
    		  n.setNext(null);
    		  last.setNext(n);
    		  last=n;
    	  }
    	  size++;
      }
      public Object get(int index) {
    	 rangeCheck(index);
    	 Node temp=first;
    	 if(first!=null) {
    		for(int i=0;i<index;i++) {
    			temp=temp.next;
    		}
    	  }
    	 return temp.obj;
       }
      
      public void rangeCheck(int index) {
    	  if(index<0||index>=size) {
    		  try {
    			throw new Exception();
    		} catch (Exception e) {
    			// TODO Auto-generated catch block
    			e.printStackTrace();
    		}
    	  }
      }
      /***
       * 在索引位置添加值
       * @param index
       * @param obj
       */
      public void add(int index,Object obj) {
    	  //根据索引查出节点
    	  Node temp=findNode(index);
    	  //创建新的节点，并赋值
    	  Node newNode=new Node();
    	  newNode.obj=obj;
    	  if(temp!=null) {
    		  //找出当前索引的前一个节点
    		  Node up=temp.pre;
    		  //将前一个节点的下一个节点赋值为新节点
    		  up.next=newNode;
    		  //将新节点的前一个节点赋值为up节点
    		  newNode.pre=up;
    		  //将新节点的下一个节点赋值temp节点
    		  newNode.next=temp;
    		  //将temp节点的前一个节点赋值为新节点
    		  temp.pre=newNode;
    		  
    		  
    		  size++;
    	  }
        }
      /**
       * 按照索引查找节点
       * @param index
       * @return
       */
    private Node findNode(int index) {
    	  Node temp=first;
    		 if(first!=null) {
    			for(int i=0;i<index;i++) {
    				temp=temp.next;
    			}
    		  }	
    		 return temp;
      }
      /**
       * 按索引删除数据
       * @param index
       */
      public void remove(int index) {
    	    rangeCheck(index);
    	    Node temp=findNode(index);
    		 
    		 if(temp!=null) {
    			 Node up=temp.pre;
    			 Node down=temp.next;
    			 up.next=down;
    			 down.pre=up;
    			 size--;
    		 }
      }
      public int size() {
    	return size;
       }
      public static void main(String[] args) {
    	
    	  MyLinkedList list=new MyLinkedList();
    	  list.add("aaa");
    	  list.add("bbbb");
    	  list.add("ccccc");
    	  list.add(1,"acassc");
    	  
    	  System.out.println(list.size());
    	  System.out.println(list.get(1));
    	  
    }
    }

## ==== ##