ArrayList 和LinkedList原理，代码实现，性能区别.
1，ArrayList 为什么查询快
数组和集合区别：动态大小，数组的长度是固定的，
ArrayList : 数组集合，内部使用数组实现的。
自定义ArrayList： 如下：
public static void main(String[] args) throws Exception {
MyArrayList myArrayList = new MyArrayList();
//添加
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
myArrayList.add(4);
myArrayList.add(5);
myArrayList.add(6);
myArrayList.add(7);
myArrayList.add(8);
myArrayList.add(9);
//修改
myArrayList.set(1,70);
//删除
myArrayList.removeAt(1);
System.out.println(myArrayList.size);
// myArrayList.clear();
for (int i=0;i<myArrayList.size;i++){
System.out.print(myArrayList.get(i) + ",");
}
}
//定义一个数组
private Object[] objects = new Object[4];
private int size = 0; //集合大小
public int size(){
return size;
}
//添加
public void add(Object value){
//判断是否可以放的下
if(size >= objects.length){
//动态扩容
Object[] temp = new Object[objects.length * 2];
// Arrays.copyOf(objects, objects.length * 2);
for (int i = 0;i< objects.length;i++){
temp[i] = objects[i];
}
objects = temp;
}
objects[size] = value;
size++;
}
//修改
public void set(int index,Object value) throws Exception{
//验证
if(index >= size || index < 0){
throw new Exception("超出范围");
}
objects[index] = value;
}
//获取
public Object get(int index) throws Exception{
//验证
if(index >= size || index < 0){
throw new Exception("超出范围");
}
return objects[index];
}
//清空
public void clear(){
size = 0;
objects = new Object[4];
}
public void removeAt(int index) throws Exception{
//验证
if(index >= size || index < 0){
throw new Exception("超出范围");
}
for (int i = index+1; i<size; i++){
objects[i-1] = objects[i];
}
size--;
}
LinkList : 底层使用链表实现 为什么查询慢..
自定义LinkedList 如下：
链表实现:包含node节点类
public static void main(String[] args) throws Exception {
MyLinkedList myLinkedList = new MyLinkedList();
//添加
myLinkedList.add(1);
myLinkedList.add(2);
myLinkedList.add(3);
myLinkedList.add(4);
myLinkedList.add(5);
myLinkedList.add(6);
myLinkedList.add(7);
myLinkedList.add(8);
myLinkedList.add(9);
//修改
myLinkedList.set(1,70);
//获取
System.out.println(myLinkedList.get(8));
//删除
myLinkedList.removeAt(1);
System.out.println(myLinkedList.size);
// myLinkedList.clear();
for (int i=0;i<myLinkedList.size;i++){
System.out.print(myLinkedList.get(i) + ",");
}
}
private int size = 0;
private Node head = null; //头 ， 链表有头什么都有， 没头什么都没有.
public int size(){
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(); //当前节点向后移动
}
//循环结束, temp表示最后一个节点
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.getNext();
}
//temp 定位到指定位置
return temp.getValue();
}
//清除
public void clear(){
head = null;
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表示删除元素的前一个元素
temp.setNext(temp.getNext().getNext());
}
size--;
}
public class Node {
private Object value; //数据
// 下一个节点地址(对象引用)
private Node next;
//构造方法
public Node(Object value) {
this.value = value;
}
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;
}
}
线性结构的列表：
-
单链表: 像马路单行线
-
单向循环链表: 像马路的单行圆盘路
-
双链表: 像马路的双行线
-
双向循环链表:像马路的双行圆盘路
LinkedList：使用的是双向循环链表实现。
ArrayList 和 LinkedList 对比:
-
添加: ArrayList 使用数组的方式添加, 向对应的位置放, 如何不扩容的话性能很高, 如果需要扩容的话就不太好了，
-
删除：ArrayList删除 ， 删除非最后一个元素，需要维护数组索引， 性能不太好了。LinkedList删除中间元素效率也是不高的，删除前面和后面的数据效率高。
-
获取和修改：ArratList通过数组索引直接定位到元素, 而LinkedList 则需要从链表头开始一直循环找到需要的元素，则性能很好。
栈和队列的代码实现
栈：先进后出，数组实现的栈(固定栈)，链表实现的栈(动态大小)
如何使用数组和单链表实现栈 push() pop() 俩个函数。
队列：先进先出，
如何使用链表实现队列 enqueue() dequeue() 俩个函数。
