성능을 비교할 자료구조는 세가지 이다.앞에서 구현한 MyArrayList, MyLinkedList 와 Java에서 구현되어 있는 LinkedList 이다.앞에서 구현한 MyLinkedList와 Java에서 구현된 LinkedList 차이점은 MyLinkedList는 List 인터페이스만 구현하였고, LinkedList는 List와 Deque 인터페이스를 구현한 이중 연결 리스트이다. 구분 MyArrayList MyLinkedList LinkedList add(끝) 1 n 1 add(시작) n 1 1 add(일반적) n n n get/set 1 n n indexOf/lastIndexOf n n n isEmpty/size 1 1 1 remove(끝) 1 n 1 remove(시작) n 1 1 remove(일반..
ArrayList
MyArrayList 구현 및 분석Java List 인터페이스를 구현한 MyArrayList를 작성123public class MyArrayList implements List { ...}Colored by Color Scriptercs get 메서드 구현1234567@Overridepublic E get(int index) { if(index = size) { throw new IndexOutOfBoundsException(); } return array[index];}Colored by Color Scriptercs=> get 메서드에 있는 모든 것은 상수 시간 set 메서드 구현123456@Overridepublic E set(int index, E element) { E old = get(inde..
ArrayListArrayList는 동적으로 크기가 늘어나는 배열이다. 그러면서도 O(1)의 접근시간(access time)을 유지한다. 배열이 가득 차는 경우, 그 크기가 두배 늘어나도록 구현되어 있다. 크기를 두배 늘리는 시간은 O(n)이지만 자주 일어나지 않기 때문에 O(1)시간이 유지된다고 보면 된다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778public class CustomArrayList { private int size = 0; private static final int ..
List 구현체 Vector 와 ArrayListList 인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 공통적인 특징을 갖는다. 공통점 차이점 List 인터페이스를 구현한다. 저장순서가 유지되고 중복을 허용한다.데이터의 저장 공간으로 배열을 사용한다. Vector는 멀티쓰레드에 대한 동기화가 되어 있으나 ArrayList는 그렇지 않다. => Vector는 동기화처리 때문에, 성능이 좋지않으므로 사용할때 주의해야 한다. LinkedList배열은 가장 기본적인 형태의 자료구조로 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간(access time)이 가장 빠르다는 장점을 가지고 있다.하지만 !! 아래와 같은 단점이 존재한다.1. 크기를 변경할 수 없다. 크기가 넘으면 새로운 배열..
