（一）ArrayList和LinkedList的原理、Java代码实现、性能比较，
（一）ArrayList和LinkedList的原理、Java代码实现、性能比较，
一、ArrayList
1.1、数组和集合的区别
动态大小，即数组的大小不可变，集合的大小可变。
ArrayList从名字上来讲是数组列表，表面上是动态大小，其底层实现原理其实还是一个数组。
1.2、简单模拟ArrayList
模拟过程中要注意Array和ArrayList的区别，数组在乎的是能装多少，而ArrayList在乎的是已经装了多少，因为ArrayList要让使用者觉得长度是可以变化的，不用担心越界什么的，但是我们写代码时，是用数组实现的，（比如要超过length时就给数组“搬家”），注意区分下面index、size和length三个变量！！！
package com.review07;
public class MyArrayList {
Object[] obj = new Object[4];
int size = 0;//集合的大小
public int getSize() {
return size;
}
//添加
public void add(Object value) {
//判断size是否达到数组的长度，若已经达到了，则要搬家，即搬到一个比现在数组长的新数组里面去
if(size >= obj.length) {
Object[] temp = new Object[obj.length*3/2+1];
//搬家
for(int i=0; i<obj.length; i++) {
temp[i] = obj[i];
}
obj = temp;
}
obj[size] = value;
size ++;
}
//判断下标是否合法
public void isIndexLegal(int index) {
if(index<0 || index>=size) { //index<0表示数组越界，index>=size超过了已放的数量，数组表示的是可放数量，我们要模拟的是已放数量
try {
throw new Exception("超出范围！");
} catch (Exception e) {
e.printStackTrace();
}
}
}
//修改下标为index的值为value
public void set(int index, Object value) {
// if(index<0 || index>=size) { //index<0表示数组越界，index>=size超过了已放的数量，数组表示的是可放数量，我们要模拟的是已放数量
// try {
// throw new Exception("超出范围！");
// } catch (Exception e) {
// e.printStackTrace();
// }
// }
isIndexLegal(index);
obj[index] = value;
}
//获取下标为index的值
public Object get(int index) {
isIndexLegal(index);
return obj[index];
}
//清除所有
public void clear() {
size = 0; //用户读不到
obj = new Object[4]; //原来的数据都会被清除掉，原来的引用没了，最终会被GC回收掉
}
//删除指定下标的值
public void removeAt(int index) {
isIndexLegal(index);
for(int i=index+1; i<size; i++) {
obj[i-1] = obj[i];
}
size --;
}
//测试
public static void main(String[] args) {
MyArrayList list = new MyArrayList();
list.add(3);
list.add(3);
list.add(2);
list.add(5);
list.add(6);
list.set(4,45);//3 3 2 5 45
list.set(4,14);//3 3 2 5 14
list.removeAt(2);//3 3 5 14
list.clear();//全部删除了
for (int i=0; i<list.getSize(); i++) {
System.out.print(list.get(i)+" ");
}
}
}
二、LinkedList
Node是结点，Joint、Connector是节点，本文可能有错别字，读者注意下！
2.1、线性结构的链表
LinkedList实际上是用双向循环链表实现的，但是双向循环链表涉及到的引用比较多，看起来比较复杂，我们可以先用单链表实现！
2.2、简单模拟单链表
首先模拟结点，结点包含数据和下一个结点的地址，Java不像C/C++，不宜直接操作地址，但是我们可以用对象的引用。
先定义一个结点类，再写自定义MyLinkedList：
package com.review07.linkedList;
public class Node {
Object value; //数据
Node next; //下一个结点的地址（对象的引用）
public Node(Object value) { //构造方法
this.value = value;
}
//添加set和get方法
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
package com.review07.linkedList;
public class MyLinkedList {
private int size =0;
private Node head = null; //头结点刚开始时空的
//获取大小
public int getSize() {
return size;
}
//在最后一个结点添加
public void add(Object value) {
Node newNode = new Node(value);
if(head == null) { //第一次添加
head = newNode;
}else {
Node temp = head; //当前结点，相当于光标
while(temp.getNext() != null) {
temp = temp.getNext(); //当前结点向后移动
}
//循环结束说明到了最后一个节点,注意添加时是添加到最后一个节点的next，而不是temp直接等于newNode
temp.setNext(newNode);
}
size ++;
}
public void set(int index, Object value) {
Node temp = head;
for(int i=0; i<index; i++) {
temp = temp.getNext();
}//temp定位到指定索引位置
temp.setValue(value);
}
public Object get(int index) {
Node temp = head;
for(int i=0; i<index; i++) {
temp = temp.next;
}
return temp.getValue();
}
//删除所有结点
public void clear() {
head = null;//头没有了，没有对象引用，gc会回收
size = 0;
}
//删除指定 结点
public void removeAt(int index) { //对头处理和对其他结点处理是不同的
if(index == 0) { //删除的是头结点
head = head.getNext();
}else { //要找到删除元素的前一个元素，这样通过要删除元素的前一个，也可以找到要删除的后一个
Node temp = head;
for(int i=0; i<index-1; i++) {
temp = temp.getNext();
}
temp.setNext(temp.getNext().getNext());
}
size --;
}
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList();
list.add(3);
list.add(3);
list.add(2);
list.add(5);
list.add(6);
list.set(4,45);//3 3 2 5 45
list.set(4,14);//3 3 2 5 14
list.removeAt(2);//3 3 5 14
//list.clear();//全部删除了
for (int i=0; i<list.getSize(); i++) {
System.out.print(list.get(i)+" ");
}
}
}
三、ArrayList和LinkedList性能比较
1.添加
ArrayList：添加是数组的方式，要考虑放不下的情况，放不下时需要先创建一个数组，再搬过去。数据少的时候没有多大影响，数据很大涉及到百万时，创建新数组+“搬家”，这显然是一个浩大的工程。
LinkedList：当数据很大涉及到百万时，用LinkedList就不一样了，用双向循环链表就很简单了，根据第一个节点就可以直接找到最后一个节点，中间有几百万个都无所谓，直接改一下引用就好了
结果：LinkedList效率高
3.删除
ArrayList：
上述例子中，若删除第二个元素，后面的元素要一个一个向前移，所以越是删前面的元素，越是耗费时间。当数据量很大时，要删前面的元素时，用ArrayList存储数据时相当不划算的。
ArrayList循环删除时（比如删除ArrayList中偶数），应该从后往前遍历删除！
（注意：删了，整体向前移了之后，数组的最后一个元素只是赋值给了它的前一个元素，没有彻底的消失，只是size--之后，我们不能访问和操作它，只能访问到它的前一个元素。）
LinkedList：
删前面或者后面的效率很高，删除中间的效率最低。
相对来说：LinkedList效率较高
3.获取和设置
ArrayList有索引，效率会比链表高的多
LinkedList用循环遍历，每循环一次，就要用引用访问一次。如果要循环遍历时，Java中用foreach，而不用for循环。
相关文章
- 暂无相关文章
用户点评