Skip to content

Commit 73c69e8

Browse files
author
tigerfour
committed
add List ...
1 parent 0815268 commit 73c69e8

File tree

6 files changed

+408
-0
lines changed

6 files changed

+408
-0
lines changed

‎group08/406166841/2-26/CustomArrayList.java

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
package net.iyouqu.bruceretrofit.util.java;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* Created by liq on 2017/2/25.
7+
*/
8+
9+
public class CustomArrayList implements List {
10+
11+
private int size = 0;
12+
13+
private final static int DEFAULT_CAPACITY = 10;
14+
private final static int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
15+
16+
private Object[] elementData = new Object[DEFAULT_CAPACITY];
17+
private String desc = "index超过界限";
18+
19+
@Override
20+
public void add(Object o) {
21+
isCapacityEnough(size + 1);
22+
elementData[size++] = o;
23+
}
24+
25+
@Override
26+
public void add(int index, Object o) {
27+
checkRangeForAdd(index);
28+
isCapacityEnough(size + 1);
29+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
30+
elementData[index] = o;
31+
size++;
32+
}
33+
34+
@Override
35+
public Object get(int index) {
36+
checkRange(index);
37+
return elementData[index];
38+
}
39+
40+
@Override
41+
public Object remove(int index) {
42+
Object value = get(index);
43+
int moveSize = size - index - 1;
44+
if (moveSize > 0){
45+
System.arraycopy(elementData,index + 1, elementData,index,size - index - 1);
46+
}
47+
elementData[--size] = null;
48+
return value;
49+
}
50+
51+
@Override
52+
public int size() {
53+
return size;
54+
}
55+
56+
private void checkRange(int index) {
57+
if (index >= size || index < 0) {
58+
throw new IndexOutOfBoundsException(desc);
59+
}
60+
}
61+
62+
private void checkRangeForAdd(int index) {
63+
if (index < 0 || index > size) {
64+
throw new IndexOutOfBoundsException(desc);
65+
}
66+
}
67+
68+
private void explicitCapacity(int capacity) {
69+
int newLength = elementData.length * 2;
70+
if (newLength - capacity < 0) {
71+
newLength = capacity;
72+
}
73+
if (newLength > (MAX_ARRAY_LENGTH)) {
74+
newLength = (capacity > MAX_ARRAY_LENGTH ? Integer.MAX_VALUE : MAX_ARRAY_LENGTH);
75+
}
76+
elementData = Arrays.copyOf(elementData, newLength);
77+
}
78+
79+
private void isCapacityEnough(int size) {
80+
if (size > DEFAULT_CAPACITY) {
81+
explicitCapacity(size);
82+
}
83+
if (size < 0) {
84+
throw new OutOfMemoryError();
85+
}
86+
}
87+
88+
public Iterator iterator() {
89+
return null;
90+
}
91+
92+
}

‎group08/406166841/2-26/CustomLinkedList.java

Lines changed: 172 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,172 @@
1+
package net.iyouqu.bruceretrofit.util.java;
2+
3+
/**
4+
* Created by liq on 2017/2/25.
5+
*/
6+
7+
public class CustomLinkedList<E> implements List {
8+
9+
//链表长度
10+
private int size = 0;
11+
//链表头指针
12+
private Node<Object> first;
13+
//链表尾部指针
14+
private Node<Object> last;
15+
//操作次数
16+
private int modCount;
17+
18+
@Override
19+
public void add(Object o) {
20+
linkLast(o);
21+
}
22+
23+
@Override
24+
public void add(int index, Object o) {
25+
checkPositionIndex(index);
26+
if (index == size) {
27+
linkLast(o);
28+
} else {
29+
linkBefore(o, node(index));
30+
}
31+
}
32+
33+
@Override
34+
public Object get(int index) {
35+
checkPositionIndex(index);
36+
return node(index).data;
37+
}
38+
39+
@Override
40+
public Object remove(int index) {
41+
checkPositionIndex(index);
42+
return unlink(node(index));
43+
}
44+
45+
@Override
46+
public int size() {
47+
return size;
48+
}
49+
50+
/**
51+
* 添加节点到链表尾部
52+
*/
53+
public void addLast(Object e) {
54+
linkLast(e);
55+
}
56+
57+
/**
58+
* 解除传入节点的属性,并且将传入节点的上一个和下一个节点 链接。使传入节点的属性 全部为 null
59+
*/
60+
private Object unlink(Node<Object> node) {
61+
//获取当前节点node的属性
62+
final Object element = node.data;
63+
final Node<Object> next = node.next;
64+
final Node<Object> prev = node.prev;
65+
if (prev == null) {
66+
//上一个节点为null将首节点设置为下一个节点
67+
first = next;
68+
} else {
69+
//上一个节点有 将上一个节点的下一个节点 设置为当前节点的下一个节点
70+
prev.next = next;
71+
//将当前节点的上一个节点设置为null
72+
node.prev = null;
73+
}
74+
if (next == null) {
75+
//下一个节点为null将末尾节点设置为上一个节点
76+
last = prev;
77+
} else {
78+
//将下一个节点的上一个节点 设置为当前节点的上一个节点
79+
next.prev = prev;
80+
node.next = null;
81+
}
82+
node.data = null;
83+
size--;
84+
modCount++;
85+
return element;
86+
}
87+
88+
/**
89+
* 获取一个节点
90+
* 判断index 在前半区间还是后半区间。而不是一直从头到尾搜索
91+
* 将节点访问复杂度从O(n)变为O(n/2)
92+
*/
93+
private Node<Object> node(int index) {
94+
checkPositionIndex(index);
95+
if (index < (size / 2)) {
96+
Node<Object> x = first;
97+
for (int i = 0; i < index; i++) {
98+
x = x.next;
99+
}
100+
return x;
101+
} else {
102+
Node<Object> x = last;
103+
for (int i = size - 1; i > index; i--) {
104+
x = x.prev;
105+
}
106+
return x;
107+
}
108+
}
109+
110+
/**
111+
* 在参数节点之前插入一个节点
112+
*/
113+
private void linkBefore(Object element, Node<Object> node) {
114+
//获取添加节点的上一个节点
115+
final Node<Object> pred = node.prev;
116+
//创建一个新节点
117+
final Node<Object> newNode = new Node<>(pred, element, node);
118+
//添加节点的上一个节点为 新节点
119+
node.prev = newNode;
120+
//判断上一个节点是否为null
121+
if (pred == null) {
122+
//首节点设置为新创建的节点
123+
first = newNode;
124+
} else {
125+
//上个节点不为null。将其下个节点设置为新创建的节点。
126+
pred.next = newNode;
127+
}
128+
size++;
129+
modCount++;
130+
}
131+
132+
/**
133+
* 链接 节点到 last
134+
*/
135+
private void linkLast(Object e) {
136+
final Node<Object> l = last;
137+
final Node<Object> newNode = new Node<>(l, e, null);
138+
last = newNode;
139+
//判断链表last是否为null
140+
if (l == null) {
141+
//链表first指向新添加的 节点
142+
first = newNode;
143+
} else {
144+
//链表last不为null将链表last节点的的next设置为新节点
145+
l.next = newNode;
146+
}
147+
size++;
148+
modCount++;
149+
}
150+
151+
/**
152+
* 检查index是否越界
153+
*/
154+
private void checkPositionIndex(int index) {
155+
if (index < 0 || index > size) {
156+
throw new IndexOutOfBoundsException("index超过界限");
157+
}
158+
}
159+
160+
private static class Node<E> {
161+
Object data;
162+
//下一个节点
163+
Node<Object> next;
164+
//上一个节点
165+
Node<Object> prev;
166+
public Node(Node<Object> prev, Object item, Node<Object> next) {
167+
this.data = item;
168+
this.next = next;
169+
this.prev = prev;
170+
}
171+
}
172+
}

‎group08/406166841/2-26/CustomQueue.java

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package net.iyouqu.bruceretrofit.util.java;
2+
3+
/**
4+
* Created by liq on 2017/2/25.
5+
*/
6+
7+
public class CustomQueue<E> {
8+
9+
Object[] data = null;
10+
//容量
11+
private int capacity;
12+
//队尾指针
13+
private int tail;
14+
15+
CustomQueue(int initSize) {
16+
if (initSize >= 0) {
17+
this.capacity = initSize;
18+
data = new Object[initSize];
19+
tail = 0;
20+
} else {
21+
throw new RuntimeException("初始化大小不能小于0" + initSize);
22+
}
23+
}
24+
25+
public void enQueue(E o){
26+
ensureCapacity();
27+
data[tail] = o;
28+
tail++;
29+
}
30+
31+
public E deQueue(){
32+
return (E) data[0];
33+
}
34+
35+
public boolean isEmpty(){
36+
return tail == 0;
37+
}
38+
39+
public int size(){
40+
return tail;
41+
}
42+
43+
private void ensureCapacity() {
44+
if (tail == capacity) {
45+
capacity *= 2;
46+
Object[] newData = new Object[capacity];
47+
System.arraycopy(data, 0, newData, 0, tail);
48+
data = newData;
49+
}
50+
}
51+
}

‎group08/406166841/2-26/CustomStack.java

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package net.iyouqu.bruceretrofit.util.java;
2+
3+
import java.util.ArrayList;
4+
5+
/**
6+
* Created by liq on 2017/2/25.
7+
*/
8+
9+
public class CustomStack<E> {
10+
11+
//重载因子
12+
private static final float LOAD_FACTOR = 0.75f;
13+
//需要扩充容量时的大小
14+
private int resizeCapacity;
15+
private Object[] data = null;
16+
//栈容量
17+
private int capacity;
18+
//栈顶
19+
private int top;
20+
21+
public CustomStack(int initSize) {
22+
if (initSize >= 0) {
23+
this.capacity = initSize;
24+
data = new Object[initSize];
25+
top = 0;
26+
this.resizeCapacity = (int) (capacity * LOAD_FACTOR);
27+
} else {
28+
throw new RuntimeException("初始化大小不能小于0:" + initSize);
29+
}
30+
}
31+
32+
private ArrayList elementData = new ArrayList();
33+
34+
public void push(E o){
35+
checkStackCapacity();
36+
data[top] = o;
37+
top++;
38+
}
39+
40+
public E pop(){
41+
if(top<=0)
42+
throw new RuntimeException("没有元素不能弹出");
43+
E e = (E) data[top - 1];
44+
data[top-1] = null;
45+
--top;
46+
return e;
47+
}
48+
49+
public E peek(){
50+
51+
return (E) data[top - 1];
52+
53+
}
54+
public boolean isEmpty(){
55+
return top == 0;
56+
}
57+
public int size(){
58+
return top;
59+
}
60+
61+
private void checkStackCapacity() {
62+
if (top == resizeCapacity) {
63+
capacity = capacity * 2;
64+
Object[] newData = new Object[capacity];
65+
System.arraycopy(data, 0, newData, 0, top);
66+
data = newData;
67+
}
68+
}
69+
70+
}

‎group08/406166841/2-26/Iterator.java

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package net.iyouqu.bruceretrofit.util.java;
2+
3+
/**
4+
* Created by liq on 2017/2/25.
5+
*/
6+
7+
public interface Iterator {
8+
public boolean hasNext();
9+
public Object next();
10+
}

0 commit comments

Comments
 (0)