ComputerScience/DataStructure (6) 썸네일형 리스트형 [DataStructure] Java에서 Linked List는 Queue와 List를 모두 사용할 수 있다. + (Iterable, Collection, List, Queue ... 요약) 코딩 테스트 문제를 풀면서 문득 'LinkedList는 List로도 사용할 수 있고, Deque로도 사용할 수 있는 것 같네' 란 생각이 들었는데요, List와 Deque를 모두 구현하고 있었군요.위 이미지는 LinkedList가 상속하고 구현하고 있는 클래스, 인터페이스 들을 다이어그램으로 표시한 그림인데요, 이 글에서는 이 LinkedList와 관련된 각 클래스, 인터페이스를 살펴보고자 합니다. IterableIterable 인터페이스는 Java에서 컬렉션을 순회하는 표준 방법을 제공한다. 이 인터페이스는 컬렉션의 요소들을 순회할 수 있도록 해준다. Iterator iterator()Iterable 인터페이스는 Java에서 컬렉션을 순회하는 표준 방법을 제공한다.주요 메서드는 다음과 같다.Iterat.. [DataStructure] Map과 Hash Table Map key-value pair들을 저장하는 ADT(Abstract Data Type)이다. key는 중복되지 않고 value는 중복될 수 있다. associative array, dictionary라고 불리기도 한다. Hash Table Hash Table(해시 테이블)은 Hash function(해시 함수)과 Array을 활용한 Map 자료 구조이며, 모든 데이터에 상수 시간 접근이 가능하다. 해시 함수의 역할은 데이터를 고정된 크기의 데이터로 변환하는 것으로, 해시 테이블에서는 데이터를 정수 값으로 변환하는 함수다. 해시 함수를 통해 값이 할당된 인덱스에 데이터를 저장하며, 배열의 크기로 모듈러 연산을 통해 인덱스 위치 지정한다. Hash Collision Hash Collision(해시 충돌)은.. [DataStructure] Array, List와 Array List, Linked List 배열(Array) 메모리의 연속된 공간에 값이 채워져 있는 형태의 자료구조 이다. 배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다. 배열은 동적으로 값을 삽입하거나 삭제하려면 본래의 값들을 이동시켜야 하는 과정이 필요해서 시간이 소요된다. 리스트(List) 리스트는 값과 포인터를 묶은 로드라는 것을 포인터로 연결한 자료구조이다. 리스트는 인덱스가 없으므로, 값에 접근하기 위해 Head 포인터에서 순서대로 접근해야 한다. 접근 시간은 느리지만, 데이터 삽입과 삭제 연산 속도는 빠르다. ADT(Abstract Data Type)에서 List는 순서가 있고 중복을 허용하는, 값들을 저장하는 추상 자료형으로 사용된다. Set이나 Map을 사용하는게 더 적절한 상황이 아니라면 .. [DataStructure] Array, Dynamic Array, Associative Array Array(배열) 배열은 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 자료 구조이다. 각 데이터는 인덱스로 접근 가능하며, 인덱스는 배열에서 오프셋 개념으로 이해된다. 인덱스는 0부터 시작하여 각 원소에 대한 위치를 가리킨다. 데이터는 연속된 메모리 공간에 할당되며, 인덱스는 해당 위치를 가리킨다. 이러한 동작 원리로 배열은 같은 타입의 데이터를 메모리에 연속적으로 저장한다. 2차원 배열은 메모리상 1차원으로 표현되며, 각 행은 메모리 주소로 구성됨. 연속적인 메모리 공간으로 데이터를 저장하면 CPU 캐시를 통해 데이터 접근 시간을 단축할 수 있음. 객체를 배열에 저장하는 경우 객체 배열은 각 객체의 레퍼런스를 연속적인 메모리 공간에 저장하고, 실제 객체들은 메모리에 띄엄띄엄 저장됨. Dynami.. [DataStructure] 우선순위 큐(Priority Queue)와 힙(Heap)의 차이 Queue Java의 Queue 인터페이스는 FIFO(First In First Out) 방식의 순차적 자료 구조를 구현 즉, 먼저 추가된 요소가 먼저 제거됨. Queue 인터페이스는 LinkedList, PriorityQueue, ArrayBlockingQueue 등 다양한 클래스에서 구현 Queue 인터페이스는 큐에 요소를 추가, 제거, 검사하는 여러 메서드를 제공하며, 다음은 가장 일반적으로 사용되는 메서드들이다. add(element): 요소를 큐의 맨 뒤에 추가, 큐가 가득 차 있으면 예외를 발생 offer(element): 요소를 큐의 맨 뒤에 추가, 큐가 가득 차 있으면 false를 반환 remove(): 큐의 앞에서 요소를 제거하고 반환, 큐가 비어 있으면 예외를 발생 poll(): 큐의 .. [DataStructure] Stack과 Queue ADT(Abstract Data Type) vs DS(Data structure) 'ADT'는 추상 자료형을 의미하며 개념적으로 어떤 동작이 있는지만 정의하고, 구현에 대해서는 다루지 않는다. 'DS'는 자료구조로, 'ADT'에서 정의된 동작을 실제로 구현한 것 Stack과 Queue는 'ADT'를 실제로 구현한 자료 구조이다. 스택(Stack)과 큐(Queue) 스택은 'Last-In-First-Out' 형태로 데이터를 저장하는 구조 데이터를 삽입하는 'push', 데이터를 뽑아내고 삭제하는 'pop', 가장 마지막에 들어온 요소를 추출하는 'peek'과 같은 동작이 있다. Queue는 'First-In-First-Out' 형태로 데이터를 저장하는 구조이며, 데이터를 삽입하는 'enqueue', 추출하.. 이전 1 다음
