java基础：ArrayList和LinkList的区别
ArrayList插入(指定位置)删除(指定位置)麻烦，查询(指定位置),更改(指定位置)容易
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
先看看本人根据ArrayList自己写的MyArrayList的代码
！！！注意：这里主要看看增删改查代码以及扩容代码即可！！！
package com.sun.ArrayList;
import java.util.Arrays;
import java.util.Collection;
/**
* 1.获取/查询指定位置元素的是时候比LinkedList快
* 3.一个对象八个字节
* 4.（1）主要运用的方法Arrays.copyOf(elementData
* ,newCapacity);（2）System.arraycopy(elementData, index, elementData, index + 1,
* size - index); 第一个为要复制的数组，第二个为从哪个开始复制，第三个为复制到哪， 第四个为复制到数组的起始位置，第五个为复制长度
* 5.扩容的时候一般情况下每次增加为原数组长度的一半，即数组长度变为原来的1.5倍。但如果增加之后大于 MAX_ARRAY_SIZE（=
* Integer.MAX_VALUE - 8），则需要根据minCapacity（最小容纳数）来决定。
* 如果minCapacity>MAX_ARRAY_SIZE
* ,则newCapacity=Integer.MAX_VALUE，minCapacity<MAX_ARRAY_SIZE
* 的话，newCapicity=MAX_ARRAY_SIZE.
*/
public class MyArrayList<E> {
/**这里介绍一下transient
* 如果用transient声明一个实例变量，当对象存储时，它的值不需要维持。换句话来说就是，
* 用transient关键字标记的成员变量不参与序列化过程 。作用：
* Java的serialization提供了一种持久化对象实例的机制。当持久化对象时
* ，可能有一个特殊的对象数据成员，我们不想用serialization机制来保存它
* 。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字transient
* 。当一个对象被序列化的时候，transient型变量的值不包括在序列化的表示中，然而非transient型的变量是被包括进去的。
*/
private transient Object[] elementData;
private int size;
// 默认的容量是10
public MyArrayList() {
this(10);
}
public MyArrayList(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal Capacity: "
+ initialCapacity);
}
this.elementData = new Object[initialCapacity];
}
public MyArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// 如果c.toArray不是对象类，则转为对象类
if (elementData.getClass() != Object[].class) {
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
}
// 将数组的初始容量变成当前容量
public void trimToSize() {
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
// 确定容量，可以容纳元素最少的数量
public void ensureCapacity(int minCapacity) {
if (minCapacity > 0) {
ensureCapacityInernal(minCapacity);
}
}
// 可以容纳至少元素的数量
private void ensureCapacityInernal(int minCapacity) {
if (elementData.length < minCapacity) {
grow(minCapacity);// 扩容
}
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;// 预留一个对象，一个对象八个字节
// 容量增长方法
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 设置容量每次的增量为原来的一半
int newCapicity = oldCapacity + (oldCapacity >> 1);
// 右移一位，值变为原来的一半，总体为原来1.5倍
// 100-->010 4-->2 。左移一位，值变为原来的二倍010-->100 2-->4
if (newCapicity < minCapacity) {
newCapicity = minCapacity;
}
if (newCapicity > MAX_ARRAY_SIZE) {
// 如果新容量比设置的最大容量还大，设置新容量时由传入的至少容量决定。
newCapicity = hugeCapacity(minCapacity);
}
elementData = Arrays.copyOf(elementData, newCapicity);
}
private int hugeCapacity(int minCapacity) {
// 如果最小容量大于设置的最大容量值，新容量等于Integer.MAX_VALUE,如果最小容量小于
// 设置的最大容量值，新容量等于设置值
if (minCapacity < 0) // overflow溢出
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i] == null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size - 1; i >= 0; i--)
if (elementData[i] == null)
return i;
} else {
for (int i = size - 1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public Object clone() {
try {
@SuppressWarnings("unchecked")
MyArrayList<E> clone = (MyArrayList<E>) super.clone();
clone.elementData = Arrays.copyOf(elementData, size);
return clone;
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
@SuppressWarnings("unchecked")
private E elementData(int index) {
return (E) elementData[index];
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("输入的值不在范围");
}
}
public E set(int index, E element) {
rangeCheck(index);
E e = (E) elementData(index);
elementData[index] = element;
return e;
}
public boolean add(E element) {
ensureCapacityInernal(size + 1);
elementData[size++] = element;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInernal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size
- index);// 第一个为要复制的数组，第二个为从哪个开始复制，第三个为复制到哪，
// 第四个为复制到数组的起始位置，第五个为复制长度
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException("输入的位置不合法");
}
public E remove(int index) {
rangeCheck(index);
E elementData2 = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0) {// 如果大于零，证明是最后一个元素之前的元素执行，这句如果不执行，
// 下面一句将表示删除最后一个元素
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
}
elementData[--size] = null;
return elementData2;
}
public boolean remove(Object o) {
if (null == o) {
for (int i = 0; i < size; i++) {
if (elementData[i] == null) {
if (size - (i + 1) > 0) {
System.arraycopy(elementData, i + 1, elementData, i,
size - (i + 1));
}
elementData[--size] = null;
return true;
}
}
} else {
for (int i = 0; i < size; i++) {
if (elementData[i].equals(o)) {
if (size - (i + 1) > 0) {
System.arraycopy(elementData, i + 1, elementData, i,
size - (i + 1));
}
elementData[--size] = null;
return true;
}
}
}
return false;
}
public void clear() {
for (int i = 0; i < size; i++) {
elementData[i] = null;
}
elementData = null;
size = 0;
}
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
ensureCapacity(size + a.length);
System.arraycopy(a, 0, elementData, size, a.length);
size = size + a.length;
return size != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] array = c.toArray();
ensureCapacity(size + array.length);
int a = size - index;
if (a > 0) {// 先将数组的前半部分和后半部分拷贝
System.arraycopy(elementData, index, elementData, index
+ array.length, a);
}
// 再将数组的中间部分插入指定的值
System.arraycopy(array, 0, elementData, index, array.length);
size = size + array.length;
return array.length != 0;
}
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r, elementData, w, size - r);
w += size - r;
}
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
size = w;
modified = true;
}
}
return modified;
}
public boolean retainAll(Collection<?> c) {
return batchRemove(c, true);
}
}再来看本人写的LinkList代码
package com.sun.LinkedList;
//插入删除的时候比ArrayList快
//用链表实现的
/*
* LinkedList插入(指定位置)删除(指定位置)容易，查询(指定位置),更改(指定位置)麻烦
* 1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
* 2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
* 3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.ListIterator;
public class MyLinkedList<E> {
public static void main(String[] args) {
MyLinkedList<String> list = new MyLinkedList<>();
list.addFirst("a");
list.addFirst("b");
list.addLast("c");
list.add("d");
list.add("e");
list.add(3, "element");
ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("5");
arrayList.add("6");
list.addAll(arrayList);
list.addAll(8, arrayList);
boolean contains = list.contains("1");
System.out.println(contains);
String string = list.get(9);
System.out.println(string);
String getfirst = list.getfirst();
String getlast = list.getlast();
System.out.println(getfirst + " " + getlast);
int indexOf = list.indexOf("6");
System.out.println(indexOf);
// list.remove(0);
// list.remove("a");
// list.removeFirst();
// list.removeLast();
list.set(9, "a");
int size2 = list.size();
System.out.println(size2);
String poll = list.poll();
System.out.println(poll);
list.printf();
}
// 加transient 不可以序列化
private transient Node<E> First;
private transient Node<E> Last;
private transient int size = 0;
public MyLinkedList() {
}
public MyLinkedList(Collection<? extends E> c) {
this();// 无参构造方法
addAll(this.size, c);
}
void printf() {
Node<E> node = First;
for (int i = 0; i < size; i++) {
if (node != null) {
System.out.print(node.element + ",");
node = node.next;
}
}
}
public E getfirst() {
if (First == null) {
System.out.println("LinkedList is null");
return null;
}
return First.element;
}
public E getlast() {
if (Last == null) {
System.out.println("LinkedList is null");
return null;
}
return Last.element;
}
public E removeFirst() {
if (IsNull()) {
System.out.println("LinkedList is null");
return null;
}
E element = First.element;
Node<E> next = First.next;
if (size == 1 && null == next) {
First = null;
Last = null;
size--;
return element;
}
First.next = null;
First.element = null;
First = next;
size--;
return element;
}
public E removeLast() {
if (IsNull()) {
System.out.println("LinkedList is null");
return null;
}
E element = Last.element;
Node<E> prev = Last.prev;
if (size == 1 && null == prev) {
Last = null;
First = null;
size--;
return element;
}
Last.prev = null;
Last.element = null;
Last = prev;
size--;
return element;
}
public void addFirst(E e) {
Node<E> node = new Node<E>(null, e, null);
if (IsNull()) {
First = node;
Last = node;
} else {
node.next = First;
First.prev = node;
First = node;
}
size++;
}
public void addLast(E e) {
Node<E> node = new Node<E>(null, e, null);
if (IsNull()) {
First = node;
Last = node;
} else {
node.prev = Last;
Last.next = node;
Last = node;
}
size++;
}
public boolean contains(Object o) {
if (indexOf(o) != -1) {
return true;
}
return false;
}
// 返回链表中第一次出现的该元素的位置
// 规定：没有这个元素的返回-1.
public int indexOf(Object o) {
int count = 0;
if (o == null) {
for (Node<E> node = First; node != null; node = node.next) {
if (node.element == o) {
return count;
}
count++;
}
} else {
for (Node<E> node = First; node != null; node = node.next) {
if (node.element.equals(o)) {
return count;
}
count++;
}
}
return -1;
}
public int size() {
return size;
}
public boolean add(E e) {
addLast(e);
return true;
}
public boolean remove(Object o) {
if (o == null) {
for (Node<E> node = First; node != null; node = node.next) {
if (node.element == null) {
if (node == First) {
removeFirst();
return true;
}
if (node == Last) {
removeLast();
return true;
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
node.element = null;
node = null;
size--;
return true;
}
}
}
} else {
for (Node<E> node = First; node != null; node = node.next) {
if (node.element.equals(o)) {
if (node == First) {
removeFirst();
return true;
}
if (node == Last) {
removeLast();
return true;
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
node.element = null;
node = null;
size--;
return true;
}
}
}
}
return false;
}
public boolean addAll(Collection<? extends E> c) {
boolean addAll = addAll(size, c);
return addAll;
}
// 向指定位置后添加一个集合
@SuppressWarnings("unchecked")
public boolean addAll(int index, Collection<? extends E> c) {
if (WithoutPosition(index)) {
Object[] array = c.toArray();
if (array.length == 0) {
return false;
}
if (index == size) {
for (int i = 0; i < array.length; i++) {
addLast((E) array[i]);
}
return true;
}
if (index == 0) {
for (int i = array.length - 1; i >= 0; i--) {
addFirst((E) array[i]);
}
return true;
} else {
for (int i = array.length - 1; i >= 0; i--) {
add(index, (E) array[i]);
}
return true;
}
}
return false;
}
private boolean WithoutPosition(int index) {
if (index >= 0 && index <= size) {
return true;
}
return false;
}
public void clear() {
for (Node<E> node = First; node != null;) {
Node<E> next = node.next;
node.prev = null;
node.next = null;
node.element = null;
node = next;
}
size = 0;
First = null;
Last = null;
}
public E get(int index) {
if (WithoutPosition(index)) {
int count = 0;
for (Node<E> node = First; node != null; node = node.next) {
if (index == count) {
return node.element;
}
count++;
}
}
return null;
}
private Node<E> getNode(int index) {
if (WithoutPosition(index)) {
int count = 0;
for (Node<E> node = First; node != null; node = node.next) {
if (index == count) {
return node;
}
count++;
}
}
return null;
}
// 将指定位置设置为指定的值
public E set(int index, E element) {
Node<E> node = getNode(index);
if (node == null) {
return null;
}
E e = node.element;
getNode(index).element = element;
return e;
}
// 在指定的位置插入元素
public void add(int index, E element) {
if (!WithoutPosition(index)) {
return;
}
if (index == 0) {
addFirst(element);
return;
}
if (index == size) {
addLast(element);
return;
} else {
InsertBefore(index, element);
}
}
private boolean InsertBefore(int index, E e) {
if (WithoutPosition(index)) {
if (index == 0) {
addFirst(e);
}
if (index == size) {
addLast(e);
}
Node<E> node = First;
Node<E> newnode = new Node<E>(null, e, null);
for (int i = 0; i < size; i++) {
if (i == index) {
Node<E> prev = node.prev;
newnode.prev = prev;
newnode.next = node;
node.prev = newnode;
prev.next = newnode;
size++;
return true;
}
node = node.next;
}
}
return false;
}
public E remove(int index) {
if (IsNull()) {
return null;
}
if (!WithoutPosition(index)) {
return null;
}
if (index == 0) {
E e = get(0);
removeFirst();
return e;
}
if (index == size - 1) {
E e = get(size - 1);
removeLast();
return e;
}
Node<E> node = getNode(index);
if (node == null) {
return null;
}
Node<E> prev = node.prev;
prev.next = node.next;
node.next.prev = prev;
node.next = null;
node.prev = null;
E e = node.element;
node.element = null;
node = null;
size--;
return e;
}
private boolean IsNull() {
if (First == null || Last == null || size == 0) {
return true;
}
return false;
}
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> node = Last; node != null; node = node.prev) {
if (node.element == null) {
return index;
}
index--;
}
} else {
for (Node<E> node = Last; node != null; node = node.next) {
if (node.element.equals(o)) {
return index;
}
index--;
}
}
return -1;
}
public E peek() {
Node<E> node = First;
return (node.element == null) ? null : node.element;
}
// 获得链表的第一个元素的值
public E element() {
return getfirst();
}
public E poll() {
Node<E> node = First;
try {
if (node.element == null) {
return null;
} else {
return node.element;
}
} finally {
removeFirst();
}
}
public E remove() {
return removeFirst();
}
public boolean offer(E e) {
return add(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
public E peekFirst() {
Node<E> f = First;
return (f == null) ? null : f.element;
}
public E peekLast() {
Node<E> l = Last;
return (l == null) ? null : l.element;
}
public E pollFirst() {
Node<E> node = First;
if (node.element == null) {
try {
return null;
} finally {
removeFirst();
}
} else {
try {
return node.element;
} finally {
removeFirst();
}
}
}
public E pollLast() {
Node<E> node = Last;
if (node.element == null) {
try {
return null;
} finally {
removeLast();
}
} else {
try {
return node.element;
} finally {
removeLast();
}
}
}
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
// 删除这个元素第一次出现的位置
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> node = Last; node != null; node = node.prev) {
if (node.element == null) {
if (node.prev == null) {
removeFirst();
} else if (node.next == null) {
removeLast();
} else {
Node<E> n = node.prev;
n.next = node.next;
node.next.prev = n;
node.element = null;
node.prev = null;
node.next = null;
node = null;
size--;
}
return true;
}
}
} else {
for (Node<E> node = Last; node != null; node = node.prev) {
if (node.element.equals(o)) {
if (node.prev == null) {
removeFirst();
} else if (node.next == null) {
removeLast();
} else {
Node<E> n = node.prev;
n.next = node.next;
node.next.prev = n;
node.element = null;
node.prev = null;
node.next = null;
node = null;
}
return true;
}
}
}
return false;
}
public Object clone() {
MyLinkedList<E> clone = superClone();
clone.Last = null;
clone.First = null;
clone.size = 0;
for (Node<E> x = First; x != null; x = x.next) {
clone.add(x.element);
}
return clone;
}
@SuppressWarnings("unchecked")
private MyLinkedList<E> superClone() {
try {
return (MyLinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = First; x != null; x = x.next)
result[i++] = x.element;
return result;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[]) java.lang.reflect.Array.newInstance(a.getClass()
.getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = First; x != null; x = x.next)
result[i++] = x.element;
if (a.length > size)
a[size] = null;
return a;
}
public ListIterator<E> listIterator(int index) {
return null;
}
@SuppressWarnings("hiding")
public class Node<E> {
Node<E> prev;
Node<E> next;
E element;
public Node(Node<E> prev, E e, Node<E> next) {
this.prev = prev;
this.element = e;
this.next = next;
}
}
}
结束，谢谢查阅。
- 列表内容