리스트 추상화 - 인터페이스 도입
List 자료 구조
순서가 있고 중복을 허용하는 자료구조를 리스트
MyArrayList 와 MyLinkedList 는 내부 구현만 다를 뿐 같은 기능을 제공
public interface List<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);
}
public class ArrayList<E> implements List<E> {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
//얼마나 만들 수 있는지
public ArrayList(){
elementData = new Object[DEFAULT_CAPACITY];
}
//초기 배열의 크기
public ArrayList(int initialCapacity){
elementData = new Object[initialCapacity];
}
@Override
public int size(){
return size;
}
@Override
//배열의 순서대로 값을 집어 넣는다.
public void add(E e) {
//size에 도달
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++;
}
private void shiftRightFrom(int index) {
for (int i = size; i > index ; i--) {
elementData[i] = elementData[i - 1];
}
}
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2;
//기존 배열 크기를 새로운 크기로 변경
//10짜리 배열을 만들고 elementData 값을 넣어준다.
elementData = Arrays.copyOf(elementData, newCapacity);
// Object[] newArr = new Object[newCapacity];
// for (int i = 0; i < elementData.length; i++) {
// //새로운 값 복사가 된다.
// newArr[i] = elementData[i];
// }
// //참조를 변경해버린다.
// elementData = newArr;
}
@Override
@SuppressWarnings("unchecked")
public E get(int index){
return (E) elementData[index];
}
@Override
//배열의 특정 위치에 값을 setting
public E set(int index, E element){
E oldVal = get(index); //기본 값을 반환
elementData[index] = element; //새로 들어온 항목을 배열에 집어 넣어 주고
return oldVal;
}
@Override
//배열에 몇번째 있는지 찾는다.
public int indexOf(Object o){
for (int i = 0; i < size; i++) {
if (o.equals(elementData[i])) {
return i;
}
}
return -1;
}
@Override
public E remove(int index) {
E oldVal = get(index);
shiftLeftFrom(index);
size--;
elementData[size] = null;
//하나씩 인덱스를 기준으로 이동 -> 마지막 값을 비워줘야 함
return oldVal;
}
//index 부터 마지막 왼쪽까지 밀기
private void shiftLeftFrom(int index) {
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i + 1];
}
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) + " size="
+ size + " capacity=" + elementData.length;
}
//Arrays.copyOf -> 배열에서 size 만큼 copy
}
public class MyArrayMyList<E> implements MyList<E> {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
//얼마나 만들 수 있는지
public MyArrayMyList(){
elementData = new Object[DEFAULT_CAPACITY];
}
//초기 배열의 크기
public MyArrayMyList(int initialCapacity){
elementData = new Object[initialCapacity];
}
@Override
public int size(){
return size;
}
@Override
//배열의 순서대로 값을 집어 넣는다.
public void add(E e) {
//size에 도달
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++;
}
private void shiftRightFrom(int index) {
for (int i = size; i > index ; i--) {
elementData[i] = elementData[i - 1];
}
}
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2;
//기존 배열 크기를 새로운 크기로 변경
//10짜리 배열을 만들고 elementData 값을 넣어준다.
elementData = Arrays.copyOf(elementData, newCapacity);
// Object[] newArr = new Object[newCapacity];
// for (int i = 0; i < elementData.length; i++) {
// //새로운 값 복사가 된다.
// newArr[i] = elementData[i];
// }
// //참조를 변경해버린다.
// elementData = newArr;
}
@Override
@SuppressWarnings("unchecked")
public E get(int index){
return (E) elementData[index];
}
@Override
//배열의 특정 위치에 값을 setting
public E set(int index, E element){
E oldVal = get(index); //기본 값을 반환
elementData[index] = element; //새로 들어온 항목을 배열에 집어 넣어 주고
return oldVal;
}
@Override
//배열에 몇번째 있는지 찾는다.
public int indexOf(Object o){
for (int i = 0; i < size; i++) {
if (o.equals(elementData[i])) {
return i;
}
}
return -1;
}
@Override
public E remove(int index) {
E oldVal = get(index);
shiftLeftFrom(index);
size--;
elementData[size] = null;
//하나씩 인덱스를 기준으로 이동 -> 마지막 값을 비워줘야 함
return oldVal;
}
//index 부터 마지막 왼쪽까지 밀기
private void shiftLeftFrom(int index) {
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i + 1];
}
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) + " size="
+ size + " capacity=" + elementData.length;
}
//Arrays.copyOf -> 배열에서 size 만큼 copy
}
public class LinkedMyList<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 lastNode = getLastNode();
lastNode.next = newNode;
}
size++; //하나가 추가 되었기 때문에 사이즈 증가.
}
public 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;//first에 newNode가 되었다고 알려준다.
//중간이나 뒷 부분에 들어가면
} else {
Node<E> prev = getNode(index - 1); //직전 노드를 찾고
newNode.next = prev.next; //직전 노드에 새 노드를 넣는다.
prev.next = newNode; //직전노드 = 새 노드
}
size++;
}
@Override
//값 setting, 예전값 가져와야 한다.
public E set(int index, E element) {
Node<E> x = getNode(index); //index에 대한 옛날 값 찾고
E oldVal = x.item;
x.item = element;
return oldVal;
}
@Override
public E remove(int index){
Node<E> removeNode = getNode(index); //삭제할 노드 찾고
E removedItem = removeNode.item; //삭제할 item 지정
if (index == 0){
first = removeNode.next; // 첫번째 위치에 삭제
//first가 아닌 경우
} 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;
}
return -1;
}
@Override
public int size(){
return size;
}
@Override
public String toString() {
return "MyLinkedListV1{" +
"first=" + first +
", size=" + size +
'}';
}
//Node 또한 GenericType 이어야 한다.
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를 활용해서 많은 데이터를 처리하는 BatchProcessor 클래스를 개발 중
데이터를 앞에서 추가 하거나 삭제하는 일이 많다면 MyArrayList 보다는 MyLinkedList 를 사용하는 것이 훨씬 효율적일 것
데이터를 앞에서 추가하거나 삭제할 때 빅오 비교
- MyArrayList : O(n)
- MyLinkedList : O(1)
MyArrayList 를 사용해보니 성능이 너무 느려서 MyLinkedList 를 사용하도록 코드를 변경해야 한다면 BatchProcessor 의 내부 코드도 MyArrayList 에서 MyLinkedList 를 사용하도록 함께 변경해야 함
BatchProcessor가 구체적 클래스에 의존하고 있다는 의미
BatchProcessor 가 구체적인 클래스에 의존하는 대신 추상적인 MyList 인터페이스에 의존 -> 다형성과 추상화 이용
public class BatchProcessor {
private final MyList<Integer> myList;
public BatchProcessor(MyList<Integer> myList) {
this.myList = myList;
}
public void logic(int size){
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
myList.add(0, i);
}
long endTime= System.currentTimeMillis();
System.out.println("크기: " + size + " 계산 시간 : " + (endTime - startTime) + " ms");
}
}
public class BatchProcessorMain {
public static void main(String[] args) {
LinkedMyList<Integer> list = new LinkedMyList<>();
//MyArrayList<Integer> list = new MyArrayList<>();
BatchProcessor batchProcessor = new BatchProcessor(list);
batchProcessor.logic(5000_000);
}
}BatchProcessor 의 외부에서 의존관계가 결정되어서 BatchProcessor 인스턴스에 들어오는 것 같다.
마치 의존관계가 외부에서 주입되는 것 같다고 해서 이것을 의존관계 주입
리스트 추상화 - 컴파일 타임, 런타임 의존관계
- 컴파일 타임 : 코드 컴파일 시점
- 런타임 : 프로그램 실행 시점 의미
컴파일 타임 의존관계는 자바 컴파일러가 보는 의존관계
클래스의 의존관계 모두 나타난다.
실행하지 않은 소스 코드에 정적으로 나타나는 의존관계
런타임 의존관계는 실제 프로그램이 작동할 때 보이는 의존관계다. 주로 생성된 인스턴스와 그것을 참조하는 의존
관계이다.
-
BatchProcessor 클래스는 구체적인 MyArrayList 나 MyLinkedList 에 의존하는 것이 아니라 추상적인 MyList 에 의존
-
리스트의 의존관계를 클래스에서 미리 결정하는 것이 아니라, 런타임에 객체를 생성하는 시점으로 미룬다. 따라서 런타임에 MyList 의 구현체를 변경해도 BatchProcessor 의 코드는 전혀 변경하지 않아도 된다.
직접 구현한 리스트의 성능 비교
public class MyListPerformanceTest {
public static void main(String[] args) {
int size = 50_000;
System.out.println("==MyArrayList 추가==");
addFirst(new MyArrayMyList<>(), size);
addMid(new MyArrayMyList<>(), size);
MyArrayMyList<Integer> myArrayList = new MyArrayMyList<>(); //조회용 데이터로 사용
addLast(myArrayList, size);
System.out.println("==MyLinkedList 추가==");
addFirst(new LinkedMyList<>(), size);
addMid(new LinkedMyList<>(), size);
LinkedMyList<Integer> linkedList = new LinkedMyList<>(); //조회용 데이터로 사용
addLast(linkedList, size);
int loop = 10000;
System.out.println("==MyArrayList 조회==");
getIndex(myArrayList, loop, 0);
getIndex(myArrayList, loop, size / 2);
getIndex(myArrayList, loop, size - 1);
System.out.println("==MyLinkedList 조회==");
getIndex(linkedList, loop, 0);
getIndex(linkedList, loop, size / 2);
getIndex(linkedList, loop, size - 1);
System.out.println("==MyArrayList 검색==");
search(myArrayList, loop, 0);
search(myArrayList, loop, size / 2);
search(myArrayList, loop, size - 1);
System.out.println("==MyLinkedList 검색==");
search(linkedList, loop, 0);
search(linkedList, loop, size / 2);
search(linkedList, loop, size - 1);
}
private static void addFirst(MyList<Integer> myList, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
myList.add(0, i);
}
long endTime = System.currentTimeMillis();
System.out.println("앞에 추가 - 크기: " + size + ", 계산 시간: " + (endTime -
startTime) + "ms");
}
private static void addMid(MyList<Integer> myList, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
myList.add(i / 2, i);
}
long endTime = System.currentTimeMillis();
System.out.println("평균 추가 - 크기: " + size + ", 계산 시간: " + (endTime -
startTime) + "ms");
}
private static void addLast(MyList<Integer> myList, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
myList.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("뒤에 추가 - 크기: " + size + ", 계산 시간: " + (endTime -
startTime) + "ms");
}
private static void getIndex(MyList<Integer> myList, int loop, int index) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < loop; i++) {
myList.get(index);
}
long endTime = System.currentTimeMillis();
System.out.println("index: " + index + ", 반복: " + loop + ", 계산 시간: " +
(endTime - startTime) + "ms");
}
private static void search(MyList<Integer> myList, int loop, int findValue) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < loop; i++) {
myList.indexOf(findValue);
}
long endTime = System.currentTimeMillis();
System.out.println("findValue: " + findValue + ", 반복: " + loop + ", 계산시간: "
+ (endTime - startTime) + "ms");
}
}
시간 복잡도와 실제 성능
- 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도등 다양한 요소에 영향
자바 리스트
List 자료 구조
순서가 있고, 중복을 허용하는 자료 구조를 리스트라 한다. 자바의 컬렉션 프레임워크가 제공하는 가장 대표적인 자료
구조가 바로 리스트이다. 리스트와 관련된 컬렉션 프레임워크는 다음 구조를 가진다.
Collection 인터페이스
자바에서 다양한 컬렉션, 즉 데이터 그룹을 다루기 위한 메서드를 정의, Collection 인터페이스는 List ,Set , Queue 와 같은 다양한 하위 인터페이스와 함께 사용
List 인터페이스
List 는 객체들의 순서가 있는 컬렉션을 나타내며, 같은 객체의 중복 저장을 허용한다. 이 리스트는 배열과 비슷하지만, 크기가 동적으로 변화
자바 ArrayList
기본 CAPACITY 는 10이다.( DEFAULT_CAPACITY = 10 )
CAPACITY 를 넘어가면 배열을 50% 증가한다.
메모리 고속 복사 연산을 사용한다.
데이터 추가 - 메모리 고속 복사 연산 사용
자바 LinkedList
단일 연결 리스트
이중 연결 리스트
node.next 를 호출하면 다음 노드로, node.prev 를 호출하면 이전 노드로 이동
데이터를 마지막에 추가하는 경우에도 O(1)의 성능을 제공
이전 노드로 이동할 수 있기 때문에 마지막 노드부터 앞으로, 그러니까 역방향으로 조회
자바 리스트의 성능 비교
package chap35.list;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class JavaListPerformanceTest {
public static void main(String[] args) {
int size = 50_000;
System.out.println("==ArrayList 추가==");
addFirst(new ArrayList<>(), size);
addMid(new ArrayList<>(), size);
MyArrayMyList<Integer> myArrayList = new MyArrayMyList<>(); //조회용 데이터로 사용
addLast(new ArrayList<>(), size);
System.out.println("==LinkedList 추가==");
addFirst(new LinkedList<>(), size);
addMid(new LinkedList<>(), size);
LinkedMyList<Integer> linkedList = new LinkedMyList<>(); //조회용 데이터로 사용
addLast(new LinkedList<>(), size);
int loop = 10000;
System.out.println("==ArrayList 조회==");
getIndex(new ArrayList<>(), loop, 0);
getIndex(new ArrayList<>(), loop, size / 2);
getIndex(new ArrayList<>(), loop, size - 1);
System.out.println("==LinkedList 조회==");
getIndex(new LinkedList<>(), loop, 0);
getIndex(new LinkedList<>(), loop, size / 2);
getIndex(new LinkedList<>(), loop, size - 1);
System.out.println("==ArrayList 검색==");
search(new ArrayList<>(), loop, 0);
search(new ArrayList<>(), loop, size / 2);
search(new ArrayList<>(), loop, size - 1);
System.out.println("== LinkedList 검색==");
search(new LinkedList<>(), loop, 0);
search(new LinkedList<>(), loop, size / 2);
search(new LinkedList<>(), loop, size - 1);
}
private static void addFirst(List<Integer> myList, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
myList.add(0, i);
}
long endTime = System.currentTimeMillis();
System.out.println("앞에 추가 - 크기: " + size + ", 계산 시간: " + (endTime -
startTime) + "ms");
}
private static void addMid(List<Integer> myList, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
myList.add(i / 2, i);
}
long endTime = System.currentTimeMillis();
System.out.println("평균 추가 - 크기: " + size + ", 계산 시간: " + (endTime -
startTime) + "ms");
}
private static void addLast(List<Integer> myList, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
myList.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("뒤에 추가 - 크기: " + size + ", 계산 시간: " + (endTime -
startTime) + "ms");
}
private static void getIndex(List<Integer> myList, int loop, int index) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < loop; i++) {
myList.get(index);
}
long endTime = System.currentTimeMillis();
System.out.println("index: " + index + ", 반복: " + loop + ", 계산 시간: " +
(endTime - startTime) + "ms");
}
private static void search(List<Integer> myList, int loop, int findValue) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < loop; i++) {
myList.indexOf(findValue);
}
long endTime = System.currentTimeMillis();
System.out.println("findValue: " + findValue + ", 반복: " + loop + ", 계산시간: "
+ (endTime - startTime) + "ms");
}
}
인덱스 조회와 검색을 제외하고는 성능개선이 된 것을 볼 수 있음.
개발자를 향해 가는 중입니다~! 항상 겸손