![]()
MyLinkedList 구현 및 분석Java List 인터페이스를 구현한 MyLinkedList를 작성 123public class MyLinkedList implements List { ..}Colored by Color Scriptercs LinkedList(연결리스트)에 대한 간단한 설명자료구조가 연결되었다 함은 노드(node)라는 객체들이 다른 노드에 대한 참조를 포함한 형태로 저장된 것을 의미한다.연결 리스트에서 각 노드는 리스트의 다음 노드에 대한 참조를 포함한다. (연결 구조의 다른 예로는 트리와 그래프가 있음)이때 노드는 둘 이상의 다른 노드에 대한 참조를 포함한다. LinkedList를 구현하려면 일단 Node를 구현해야 하는데, MyLinkedList 안에 inner class로 Nod..
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..
StringBuffer아래의 코드를 살펴보자1234567public String joinWords(String[] words) { String sentence = ""; for(String word : words) { sentence += word; } return sentence;}Colored by Color Scriptercs이 코드는 문자열 배열을 하나로 합쳐서 리턴해주는 함수이다. 언뜻보아서는 아무런 문제가 없어보이지만 이 코드의 실행 시간은 어떻게 될까?간단하게 문자열 길이는 전부 x라고 하고 문자열 개수는 n이라고 해보자. 문자열을 연결할때 마다 새로운 문자열 객체가 만들어지고 (sentence), 연결할 문자열의 값이 문자 단위로 복사된다. 그러므로 첫 번째 루프에서 x개의 문자가 복사되고..
ArrayListArrayList는 동적으로 크기가 늘어나는 배열이다. 그러면서도 O(1)의 접근시간(access time)을 유지한다. 배열이 가득 차는 경우, 그 크기가 두배 늘어나도록 구현되어 있다. 크기를 두배 늘리는 시간은 O(n)이지만 자주 일어나지 않기 때문에 O(1)시간이 유지된다고 보면 된다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778public class CustomArrayList { private int size = 0; private static final int ..
![]()
해시 테이블해시 테이블(hash table)은 효율적인 탐색을 위한 자료구조로 키(key)를 값(value)에 대응시킨다. 해시 테이블을 간단히 구현하는 경우, 배열과 해시 함수(hash function)만 있으면 된다.객체와 키를 해시 테이블에 저장할 경우, 해시 함수가 키를 정수값으로 대응 시키는데, 이 정수 값이 배열의 첨자(index)로 쓰인다. 객체는 배열의 해당 첨자 위치에 저장된다.하지만.. 이것은 정상적으로 작동하지 않을 수 있다. 왜냐하면 해시 함수가 계산하는 모든 키 값이 유일(unique)해야 하기 때문이다. 해시함수 후에 나오는 결과가 동일한 결과가 나올 경우 우리는 이것을 충돌(collision)이라고 한다. 충돌(collision)을 피하려면 모든 키 값을 고려해서 배열을 극도로..
