S E P H ' S

Doubly LinkedList 실제 자바에서 제공하는 util 패키지의 LinkedList는 이번에 구현할 Doubly LinkedList와 같은 형식으로 구현되어 있다. 단일 연결리스트와 차이점은 단일 연결리스트는 노드에 데이터, 다음 노드를 가리킬 변수만을 갖고 있었다면 이중 연결리스트는 이전 노드를 가리키는 변수도 갖고 있다. 전체적인 구조는 다음과 같다. 양방향 연결리스트는 단방향 연결리스트보다 검색(색인)능력이 좋아진다. 단방향 연결리스트에서는 head부터 탐색했어야 했다. 하지만 양방향 연결리스트에서는 찾으려는 값이 만약 tail에 더 가깝다면 tail부터 탐색하면 되고 head에 더 가깝다면 head부터 탐색하면 되므로 보다 더 효율적인 탐색이 가능하다. Node 구현 public clas..

Singly LinkedList ArrayList와 가장 큰 차이점은 '노드'라는 객체를 이용하여 연결하는 것. ArrayList의 경우 최상위 타입인 Object[] 을 사용하여 데이터를 담았다면 LinkedList는 배열을 이용하는 것이 아닌 하나의 객체를 두고 그 안에 데이터와 다른 노드를 가리키는 레퍼런스 데이터로 구성하여 여러 노드를 하나의 체인처럼 연결하는 것이다. Node 데이터와 다른 노드를 가리키는 주소데이터를 담을 객체 LinkedList의 가장 기초적 단위 배열과 LinkedList의 구조 비교 위 그림에서 보면 각각의 레퍼런스 변수는 다음 노드 객체를 가리키고 있다. 이렇게 단방향으로 연결된 리스트를 Singly LinkedList라고 한다. 한 마디로 노드들을 연결시킨 형태가 바로..

ArrayList ArrayList는 다른 자료구조와 달리 Object[] 배열, 즉 객체 배열을 두고 사용한다. 모든 자료구조는 '동적 할당'을 전제로 한다. 동적 할당을 안하고 사이즈를 정해놓고 구현한다면 메인함수에서 정적 배열을 선언하는 것과 차이가 없다. 데이터의 개수를 알 수 없는데 배열을 쓰고 싶을 때 ArrayList, LinkedList 등의 자료구조를 선택한다. 데이터 사이에 빈 공간을 허락하지 않는다. 항상 리스트 계열 자료구조는 데이터들이 '연속적'이어야 한다. ArrayList 구현 클래스 및 생성자 구성 resize 메소드 구현 add 메소드 구현 get, set, indexOf, contains 메소드 구현 remove 메소드 구현 size, isEmpty, clear 메소드 구..

자료구조란? 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현 방법들이다. 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 된다. 데이터의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있다. 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 중요하다. List Interface 자바 컬렉션 프레임워크(Collection(List, Map, Set), Collection(Stack, Queue))에서 지원하는 ArrayList, LinkedList 같은 리스트 클래스들은 우리가 조금더 데이터들을 다루기 쉽도록 메소드들을 구현한 것이다. 공통점 동일한 특성의 데이터들을 묶는다. 반복문 내에 변수를 이용하여 하나의 묶음 데이터들..