public interface MyList<E> {
int size();
void add(E e);
void add(int index, E e);
E get(int index);
E set(int index, E element);
E remove(int index);
int indexOf(E o);
}
package collection.list;
import java.util.Arrays;
public class MyarrayList<E> implements MyList<E> {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyarrayList() {
elementData = new Object[DEFAULT_CAPACITY];
}
public MyarrayList(int initialCapacity) {
elementData = new Object[initialCapacity];
}
@Override
public int size() {
return size;
}
@Override
public void add(E e) {
if (size == elementData.length) {
grow();
}
elementData[size] = e;
size++;
}
@Override
public void add(int index, E e) {
if (size == elementData.length) {
grow();
}
shiftRightFrom(index);
elementData[index] = e;
size++;
}
//요소의 마지막부터 index까지 오른쪽으로 밀기
private void shiftRightFrom(int index) {
for (int i = size; i > index; i--) {
elementData[i] = elementData[i - 1];
}
}
@SuppressWarnings("unchecked")
@Override
public E get(int index) {
return (E) elementData[index];
}
@Override
public E set(int index, E element) {
E oldValue = get(index);
elementData[index] = element;
return oldValue;
}
@Override
public E remove(int index) {
E oldValue = get(index);
shiftLeftFrom(index);
size--;
elementData[size] = null;
return oldValue;
}
//요소의 index부터 마지막까지 왼쪽으로 밀기
private void shiftLeftFrom(int index) {
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i + 1];
}
}
@Override
public int indexOf(E o) {
for (int i = 0; i < size; i++) {
if (o.equals(elementData[i])) {
return i;
}
}
return -1;
}
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2;
elementData = Arrays.copyOf(elementData, newCapacity);
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) +
" size=" + size + ", capacity=" + elementData.length;
}
}
package collection.list;
public class MyLinkedList<E> implements MyList<E>{
private Node<E> first;
private int size = 0;
@Override
public void add(E e) {
Node<E> newNode = new Node<>(e);
if (first == null) {
first = newNode;
} else {
Node<E> lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
private Node<E> getLastNode() {
Node<E> x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
@Override
public void add(int index, E e) {
Node<E> newNode = new Node<>(e);
if (index == 0) {
newNode.next = first;
first = newNode;
} else {
Node<E> prev = getNode(index - 1);
newNode.next = prev.next;
prev.next = newNode;
}
size++;
}
@Override
public E set(int index, E element) {
Node<E> x = getNode(index);
E oldValue = x.item;
x.item = element;
return oldValue;
}
@Override
public E remove(int index) {
Node<E> removeNode = getNode(index);
E removedItem = removeNode.item;
if (index == 0) {
first = removeNode.next;
} else {
Node<E> prev = getNode(index - 1);
prev.next = removeNode.next;
}
removeNode.item = null;
removeNode.next = null;
size--;
return removedItem;
}
@Override
public E get(int index) {
Node<E> node = getNode(index);
return node.item;
}
private Node<E> getNode(int index) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
@Override
public int indexOf(E o) {
int index = 0;
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
return -1;
}
@Override
public int size() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV1{" +
"first=" + first +
", size=" + size +
'}';
}
private static class Node<E> {
E item;
Node<E> next;
public Node(E item) {
this.item = item;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node<E> temp = this;
sb.append("[");
while (temp != null) {
sb.append(temp.item);
if (temp.next != null) {
sb.append("->");
}
temp = temp.next;
}
sb.append("]");
return sb.toString();
}
}
}
데이터를앞에서추가하거나삭제하는일이많다면`MyArrayList`보다는`
MyLinkedList` 를사용하는것이훨씬효율적이다.
**데이터를앞에서추가하거나삭제할때빅오비교**
`MyArrayList` : O(n)
`MyLinkedList` : O(1)
다음코드를 통해 비교해보자
public class BatchProcessor {
private MyList<Integer> list;
public BatchProcessor(MyList<Integer> e) {
list=e;
}
public void logic(int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(0,i);
}
long endTime = System.currentTimeMillis();
System.out.println("앞에 데이터"+size+"번 추가하는 데 걸리는 시간 : "
+((endTime-startTime))+"ms");
}
}
public class BatchProcessorMain {
public static void main(String[] args) {
BatchProcessor arrayBatch = new BatchProcessor(new MyarrayList<>());
BatchProcessor linkedBatch= new BatchProcessor(new MyLinkedList<>());
arrayBatch.logic(49999);
linkedBatch.logic(49999);
}
}
MyArrayList<Integer> list = new MyArrayList<>();
BatchProcessor processor = new BatchProcessor(list);
processor.logic(50_000);
`BatchProcessor` 인스턴스의 `MyList list` 는 생성자를 통해 `MyArrayList(x001)` 인스턴스를 참조한
다.
`BatchProcessor` 인스턴스에 `MyArrayList(x001)` 의존관계를 주입한다.
따라서 이후 `logic()` 을 호출하면 `MyArrayList` 인스턴스를 사용하게 된다.
**Item 클래스**
```java
package collection.list.test.ex2;
public class Item {
private String name;
private int price;
private int quantity;
public Item(String name, int price, int quantity) {
this.name = name;
this.price = price;
this.quantity = quantity;
}
public String getName() {
return name;
}
public int getTotalPrice() {
return price * quantity;
}
}
public class ShoppingCartMain {
public static void main(String[] args) {
Shoppingcart cart = new Shoppingcart();
Item item1 =new Item("상추", 1200, 5);
Item item2 =new Item("마늘", 3200, 2);
Item item3 =new Item("대파", 2500, 5);
cart.add(item1);
cart.add(item2);
cart.add(item3);
cart.displayItem();
}
}
출력 예시
상품명 : xx 가격 : xxxx
총 가격 : xxx
배열을 사용한 ShoppingCart클래스(배열)
public class Shoppingcart2 {
int total;
int itemCount;
Item[] items = new Item[10];
public void add(Item item1) {
if(itemCount >= items.length) {
System.out.println("장바구니가 가득 찼어요");
return;
}
items[itemCount] = item1;
System.out.println("장바구니에 담았어요 , 현재수량 : "+(itemCount+1));
itemCount++;
}
public void displayItem() {
for (int i = 0; i < itemCount; i++) {
Item item = items[i];
System.out.println("상품명 : "+item.getName()
+" 가격 : "+item.totalPrice());
total+=item.totalPrice();
}
System.out.println("총 가격 : "+total);
}
}
완성한Shoppingcart 클래스(리스트)
public class Shoppingcart {
int total;
ArrayList<Item> list = new ArrayList<>();
public void add(Item item1) {
list.add(item1);
}
public void displayItem() {
for (Item item : list) {
System.out.println("상품명 : "+item.getName()+
" 합계 : "+item.totalPrice());
total+=item.totalPrice();
}
System.out.println("총 구매 금액 : "+total);
}
}
