ArrayList和LinkedList

2018-07-12 07:34:28来源：博客园阅读 ()

集合List下有2个子类，分别为ArrayList和LinkedList。

ArrayList:里面实际为数组，动态大小。即创建ArrayList时自动创建数组大小，在后续添加数据时，数组长度不够，会自动进行扩容。连续内存，增修查快、删除慢。下方分别是图形展示和部分实现代码。

 1 public class MyArrayList {
 2 
 3     Object[] objs = new Object[4];
 4     
 5     int size = 0;
 6     
 7     public void add(Object value) {
 8         
 9         //判断容量是否足够大，不够进行扩容
10         if(size >= objs.length) {
11             Object[] temp = new Object[objs.length*2];
12             
13             for(int i=0; i<objs.length; i++) {
14                 temp[i] = objs[i];
15             }
16         }
17         
18         objs[size] = value;
19         size++;
20     }
21     
22 }

View Code

LinkedList:是不连续的内存，由数组和下一个结点的地址组成，头会特别标记，增修查慢、删除快。下方分别是图形展示和部分实现代码。

 1 //LinkedList中需要使用
 2 public class MyNode {
 3     
 4     Object value; //数据
 5     
 6     MyNode next;
 7     
 8     public MyNode(Object value) {
 9         this.value = value;
10     }
11 
12     public Object getValue() {
13         return value;
14     }
15 
16     public void setValue(Object value) {
17         this.value = value;
18     }
19 
20     public MyNode getNext() {
21         return next;
22     }
23 
24     public void setNext(MyNode next) {
25         this.next = next;
26     }
27     
28 }

View Code

 1 public class MyLinkedList {
 2     
 3     int size = 0;
 4     //换门标记第一个元素
 5     MyNode head = null;
 6     
 7     public void add(Object value) {
 8         MyNode node = new MyNode(value);
 9         
10         if(null == head) {
11             head = node;
12         }else {
13             MyNode temp = head;
14             
15             //得到最后一个结点,并把新的结点追加进去
16             while(null != temp.getNext()) {
17                 temp = temp.getNext();
18             }
19             temp.setValue(value);
20         }
21     }
22 }