Java 集合的简单实现 (ArrayList & LinkedList & Queue

发布时间：2020-12-14 06:32:58 所属栏目：Java 来源：网络整理

导读：ArrayList 就是数组实现的啦，没什么好说的，如果数组不够了就扩容到原来的1.5倍实现了迭代器 span style="color: #0000ff;"import span style="color: #000000;" java.io.Serializable; span style="color: #0000ff;"import span style="color: #000000;"

ArrayList

就是数组实现的啦，没什么好说的，如果数组不够了就扩容到原来的1.5倍

实现了迭代器

import java.io.Serializable;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.RandomAccess;

/**

@author wenr
实现方法：
- void add(E e)
- void add(int index,E e)
- E get(int index)
- int indexOf(Object o)
- boolean contains(Object o)
- int size()
- boolean isEmpty()
- E remove(int index)
- boolean remove(Object o)
- Iterator iterator()
*/
public class ArrayListDemo implements RandomAccess,Cloneable,Serializable{

private static final int DEFAULT_SIZE = 10;

private Object[] elementData;
private int size = 0;

ArrayListDemo() {
this(DEFAULT_SIZE);
}

ArrayListDemo(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("初始化参数错误：" + initialCapacity);
} else {
elementData = new Object[initialCapacity];
}
}

public void add(E e) {
isCapacityEnough(size + 1);
elementData[size++] = e;
}

public void add(int index,E e) {
rangeCheckForAdd(index);
isCapacityEnough(size + 1);
System.arraycopy(elementData,index,elementData,index + 1,size - index);
elementData[index] = e;
size++;
}

private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("下标越界：" + index);
}

private void isCapacityEnough(int capacity) {
// 溢出
if (capacity < 0)
throw new OutOfMemoryError();
// 需要扩容
if (capacity - elementData.length > 0)
grow(capacity);
}

private void grow(int capacity) {
int oldCapacity = elementData.length;
// 设置新容量是原容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 可能会有一次加入多个数据的情况那么久直接加到所需容量
if (capacity - newCapacity > 0)
newCapacity = capacity;
elementData = Arrays.copyOf(elementData,newCapacity);
}

public E get(int index) {
rangeCheck(index);
return (E)elementData[index];
}

private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("下标越界：" + index);
}

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 boolean contains(Object o) {
return indexOf(o) >= 0;
}

public int size() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

public E remove(int index) {
rangeCheck(index);
E value = (E)elementData[index];
int moveSize = size - index - 1;
if (moveSize > 0)
System.arraycopy(elementData,index + 1,moveSize);
elementData[--size] = null;
return value;
}

public boolean remove(Object o) {
int index = indexOf(o);
if (index < 0) {
return false;
} else {
remove(index);
return true;
}
}

public Iterator iterator() {
return new Itr();
}

private class Itr implements Iterator {
```
 cursor = 0; 
```

@Override
public boolean hasNext() {
return cursor != size;
}
```
 @Override
 (cursor < 0 || cursor >= = ArrayListDemo. (E)elementData[cursor++public static void main(String[] args) {
ArrayListDemo list = new ArrayListDemo();
list.add("1");
list.add("2");
list.add("3");
System.out.println(list.get(0));
System.out.println(list.get(1));
System.out.println(list.get(2));
System.out.println(list.indexOf("3"));
System.out.println(list.remove("3"));
System.out.println(list.contains("3"));
// System.out.println(list.get(3));
Iterator itr = list.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
}

}

LinkedList

嗯，就是一个双向链表~

import java.util.Iterator;
import java.util.NoSuchElementException;

/**

@author wenr
实现方法:
- void add(E e)
- void add(int index,E e)
- E get(int index)
- int indexOf(Object o)
- boolean contains(Object o)
- E remove(int index)
- boolean remove(Object o)
- boolean isEmpty()
- int size()
- Iterator iterator()
*/
public class LinkedListDemo {

private int size;
Node first;
Node last;

public LinkedListDemo() {
}

// 添加一个节点在结尾处
public void add(E e) {
Node l = last;
Node node = new Node(e,last,null);
last = node;
if (l == null) {
first = node;
} else {
l.next = node;
}
size++;
}

public void add(int index,E e) {
rangeCheckForAdd(index);
if (index == size) {
add(e);
} else {
Node x = node(index);
addBeforeNode(e,x);
}
}

private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("下标越界：" + index);
}

private void addBeforeNode(E e,Node beforeNode) {
Node preNode = beforeNode.prev;
Node newNode = new Node(e,preNode,beforeNode);
if (preNode == null) {
first = newNode;
} else {
preNode.next = newNode;
}
beforeNode.prev = newNode;
size++;
}

private Node node(int index) {
// 如果node在前一半就正向查找否则逆向查找
if (index < (size >> 1)) {
Node cursor = first;
for (int i = 0; i < index; ++i) {
cursor = cursor.next;
}
return cursor;
} else {
Node cursor = last;
for (int i = size-1; i > index; --i) {
cursor = cursor.prev;
}
return cursor;
}
}

public E get(int index) {
rangeCheck(index);
Node x = node(index);
return x.item;
}

private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("数组越界：" + index);
}

public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}

public E remove(int index) {
rangeCheck(index);
```
 Node<E> x = E element = Node<E> prev = Node<E> next = (prev == === (next == === = --public boolean remove(Object o) {
int index = indexOf(o);
if (index < 0)
return false;
remove(index);
return true;
}

public int size() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

public boolean contains(Object o) {
return indexOf(o) >= 0;
}

public Iterator iterator() {
return new Itr();
}

private static class Node {
E item;
Node prev;
Node next;
public Node(E item,Node prev,Node next) {
this.item = item;
this.prev = prev;
this.next = next;
}
}

private class Itr implements Iterator {
```
 Node<E> == 0 nextIndex < (! ==++public static void main(String[] args) {
LinkedListDemo list = new LinkedListDemo<>();
list.add("aaaa");
list.add("bbbb");
list.add("cccc");
list.add("dddd");
System.out.println(list.size());
System.out.println(list.get(1));
System.out.println(list.get(2));
System.out.println(list.get(0));
System.out.println(list.remove(2));
list.add(3,"eeee");
System.out.println(list.get(1));
System.out.println(list.get(2));
System.out.println(list.get(3));
System.out.println("_____");
Iterator itr = list.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
}

}

Queue

瞎写的啦哈哈哈

队列先进先出用循环队列实现节省空间

当front==tail就是队列为空

因为如果队列全部装满的时候front==tail，和空一样，所以循环队列不能全部装满，至少空出一位

当(tail+1)%capacity==front的时候就是队列满（capacity是队列容量大小

import java.util.Arrays;
import java.util.NoSuchElementException;

/**

@author wenr
通过数组实现的循环队列
实现方法：
- boolean offer(E)
- boolean isEmpty()
- E peek()
- E poll()
- int size()
*/

public class QueueDemo {

</span><span style="color: #0000ff;"&gt;private</span> <span style="color: #0000ff;"&gt;static</span> <span style="color: #0000ff;"&gt;final</span> <span style="color: #0000ff;"&gt;int</span> DEFAULT_SIZE = 0<span style="color: #000000;"&gt;;

</span><span style="color: #0000ff;"&gt;private</span><span style="color: #000000;"&gt; Object[] elementData;
</span><span style="color: #0000ff;"&gt;private</span> <span style="color: #0000ff;"&gt;int</span><span style="color: #000000;"&gt; front;
</span><span style="color: #0000ff;"&gt;private</span> <span style="color: #0000ff;"&gt;int</span><span style="color: #000000;"&gt; tail;

</span><span style="color: #0000ff;"&gt;public</span><span style="color: #000000;"&gt; QueueDemo() {
    </span><span style="color: #0000ff;"&gt;this</span><span style="color: #000000;"&gt;(DEFAULT_SIZE);
}

</span><span style="color: #0000ff;"&gt;public</span> QueueDemo(<span style="color: #0000ff;"&gt;int</span><span style="color: #000000;"&gt; capacity) {
    elementData </span>= <span style="color: #0000ff;"&gt;new</span><span style="color: #000000;"&gt; Object[capacity];
    front </span>= tail = 0<span style="color: #000000;"&gt;;
}

</span><span style="color: #008000;"&gt;//</span><span style="color: #008000;"&gt; 向队列中加入一个元素</span>
<span style="color: #0000ff;"&gt;public</span> <span style="color: #0000ff;"&gt;boolean</span><span style="color: #000000;"&gt; offer(E element) {
    </span><span style="color: #0000ff;"&gt;int</span> capacity =<span style="color: #000000;"&gt; elementData.length;
    </span><span style="color: #008000;"&gt;//</span><span style="color: #008000;"&gt; 注意这里是capacity-1哦  因为要区别empty 所以循环队列不能装满的</span>
    <span style="color: #0000ff;"&gt;if</span> (size() == capacity - 1<span style="color: #000000;"&gt;) {
        grow(</span>++<span style="color: #000000;"&gt;capacity);
    }
    elementData[tail] </span>=<span style="color: #000000;"&gt; element;
    tail </span>= (tail + 1) %<span style="color: #000000;"&gt; capacity;
    </span><span style="color: #0000ff;"&gt;return</span> <span style="color: #0000ff;"&gt;true</span><span style="color: #000000;"&gt;;
}

</span><span style="color: #008000;"&gt;//</span><span style="color: #008000;"&gt; 获取并移除此队列的头</span>
<span style="color: #0000ff;"&gt;public</span><span style="color: #000000;"&gt; E poll() {
    </span><span style="color: #0000ff;"&gt;if</span><span style="color: #000000;"&gt; (isEmpty())
        </span><span style="color: #0000ff;"&gt;throw</span> <span style="color: #0000ff;"&gt;new</span><span style="color: #000000;"&gt; NoSuchElementException();
    E element </span>=<span style="color: #000000;"&gt; (E)elementData[front];
    front </span>= (front + 1) %<span style="color: #000000;"&gt; elementData.length;
    </span><span style="color: #0000ff;"&gt;return</span><span style="color: #000000;"&gt; element;
}

</span><span style="color: #0000ff;"&gt;private</span> <span style="color: #0000ff;"&gt;void</span> grow(<span style="color: #0000ff;"&gt;int</span><span style="color: #000000;"&gt; capacity) {
    </span><span style="color: #0000ff;"&gt;if</span> (capacity == -1<span style="color: #000000;"&gt;)
        </span><span style="color: #0000ff;"&gt;throw</span> <span style="color: #0000ff;"&gt;new</span><span style="color: #000000;"&gt; OutOfMemoryError();

    </span><span style="color: #0000ff;"&gt;int</span> oldCapacity =<span style="color: #000000;"&gt; elementData.length;
    </span><span style="color: #0000ff;"&gt;int</span> newCapacity = oldCapacity + (oldCapacity >> 1<span style="color: #000000;"&gt;);
    </span><span style="color: #0000ff;"&gt;if</span> (newCapacity <<span style="color: #000000;"&gt; capacity)
        newCapacity </span>=<span style="color: #000000;"&gt; capacity;
    </span><span style="color: #0000ff;"&gt;if</span> (front <<span style="color: #000000;"&gt; tail) {
        </span><span style="color: #008000;"&gt;//</span><span style="color: #008000;"&gt; [front...tail]</span>
        elementData =<span style="color: #000000;"&gt; Arrays.copyOf(elementData,newCapacity);
    } </span><span style="color: #0000ff;"&gt;else</span><span style="color: #000000;"&gt; {
        </span><span style="color: #008000;"&gt;//</span><span style="color: #008000;"&gt; [...tail front...]</span>
        Object[] tempData = <span style="color: #0000ff;"&gt;new</span><span style="color: #000000;"&gt; Object[newCapacity];
        </span><span style="color: #0000ff;"&gt;int</span> moveSize = oldCapacity -<span style="color: #000000;"&gt; front;
        System.arraycopy(elementData,front,tempData,</span>0<span style="color: #000000;"&gt;,moveSize);
        System.arraycopy(elementData,moveSize,tail);
        elementData </span>=<span style="color: #000000;"&gt; tempData;
        tempData </span>= <span style="color: #0000ff;"&gt;null</span><span style="color: #000000;"&gt;;
        front </span>= 0<span style="color: #000000;"&gt;;
        tail </span>= oldCapacity - 1<span style="color: #000000;"&gt;;
    }

}

</span><span style="color: #008000;"&gt;//</span><span style="color: #008000;"&gt; 获取但不移除此队列的头</span>
<span style="color: #0000ff;"&gt;public</span><span style="color: #000000;"&gt; E peek() {
    </span><span style="color: #0000ff;"&gt;if</span><span style="color: #000000;"&gt; (isEmpty())
        </span><span style="color: #0000ff;"&gt;throw</span> <span style="color: #0000ff;"&gt;new</span><span style="color: #000000;"&gt; NoSuchElementException();
    </span><span style="color: #0000ff;"&gt;else</span> 
        <span style="color: #0000ff;"&gt;return</span><span style="color: #000000;"&gt; (E)elementData[front];
}

</span><span style="color: #0000ff;"&gt;public</span> <span style="color: #0000ff;"&gt;boolean</span><span style="color: #000000;"&gt; isEmpty() {
    </span><span style="color: #0000ff;"&gt;return</span> front ==<span style="color: #000000;"&gt; tail;
}

</span><span style="color: #0000ff;"&gt;public</span> <span style="color: #0000ff;"&gt;int</span><span style="color: #000000;"&gt; size() {
    </span><span style="color: #0000ff;"&gt;int</span> capacity =<span style="color: #000000;"&gt; elementData.length;
    </span><span style="color: #0000ff;"&gt;return</span> (tail - front + capacity) %<span style="color: #000000;"&gt; capacity;
}

</span><span style="color: #0000ff;"&gt;public</span> <span style="color: #0000ff;"&gt;static</span> <span style="color: #0000ff;"&gt;void</span><span style="color: #000000;"&gt; main(String[] args) {
    QueueDemo</span><Integer> q = <span style="color: #0000ff;"&gt;new</span> QueueDemo<>(5<span style="color: #000000;"&gt;);
    q.offer(</span>1<span style="color: #000000;"&gt;);
    q.offer(</span>2<span style="color: #000000;"&gt;);
    q.offer(</span>3<span style="color: #000000;"&gt;);
    q.offer(</span>4<span style="color: #000000;"&gt;);
    System.out.println(q.poll());
    System.out.println(q.poll());
    q.offer(</span>5<span style="color: #000000;"&gt;);
    q.offer(</span>6<span style="color: #000000;"&gt;);
    q.offer(</span>7<span style="color: #000000;"&gt;);
    q.offer(</span>8<span style="color: #000000;"&gt;);
    </span><span style="color: #0000ff;"&gt;while</span> (!<span style="color: #000000;"&gt;q.isEmpty()) {
        System.out.print(q.peek() </span>+ " "<span style="color: #000000;"&gt;);
        q.poll();
    }
    </span><span style="color: #008000;"&gt;//</span><span style="color: #008000;"&gt;q.poll();</span>

}
}

Stack

哦还是瞎写的

栈先进后出没什么好说的都比较简单

import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Stack;

/**

@author wenr
实现函数：
- E peek()
- E pop()
- void push(E)
- isEmpty()
- size()
*/
public class StackDemo {
private static final int DEFAULT_SIZE = 10;
private int top;
private Object[] data;

public StackDemo() {
this(DEFAULT_SIZE);
}

public StackDemo(int capacity) {
data = new Object[capacity];
}

public E peek() {
if (isEmpty())
throw new NoSuchElementException();
return (E)data[top - 1];
}

public E pop() {
if (isEmpty())
throw new NoSuchElementException();
return (E)data[--top];
}

public void push(E e) {
int capacity = data.length;
if (top == capacity) {
grow(capacity + 1);
}
data[top++] = e;
}

private void grow(int capacity) {
if (capacity <= 0)
throw new OutOfMemoryError();
int oldCapacity = data.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity < capacity) {
newCapacity = capacity;
}
data = Arrays.copyOf(data,newCapacity);
}

public boolean isEmpty() {
return top == 0;
}

public int size() {
return top;
}

public static void main(String[] args) {
StackDemo stack = new StackDemo<>(3);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.pop();
stack.push(7);
while (!stack.isEmpty()) {
System.out.println(stack.peek());
stack.pop();
}
}

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

Java 集合的简单实现 (ArrayList &amp; LinkedList &amp; Queue

Java 集合的简单实现 (ArrayList & LinkedList & Queue