자료구조 (8) 썸네일형 리스트형 Hash • 데이터를 빠르게 저장하고 가져오는 기법 중 하나 해시 함수 (짧게는 그냥 해시)는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수를 말한다. 쉽게 말해, 아무리 큰 숫자를 넣더라도 정해진 크기의 숫자가 나오는 함수이다. 위의 1,3번째 "Hello" 는 hashcode 적용 하더라도 같은 데이터를 추출한다. Hash Table key-value 데이터들의 모음집 ⇒ key 를 이용하여, 데이터를 저장하거나 or 꺼내온다 아래의 예시는 데이터가 Hash Table에 어떻게 저장되는지를 그림으로 표현한다. Key Value John Smith 521-1234 Lisa Smith 521-8976 Sandra Dee 521-9655 Key = (”John Smith”) Key.. Queue(원형 큐 : Circular Queue) 이전 선형 큐 글에서 "선형큐를 Array 로 구현했을때, 상당히 비효율적이다" 라고 이야기 했었다. 원형 큐는 큐를 Array로 구현하되 Array로 구현했을때 일어나는 단점을 보완한 자료구조이다. front 와 rear 의 index 모두가 같은 인덱스를 가리키고 있다면, 해당 Circular Queue 는 비어있는 것이다. 데이터를 넣을 때 rear 인덱스 이동 데이터를 추가할 경우 1. front 는 정지해 있고, 2. rear 만 1칸씩 움직이면서, 데이터를 추가한다.(Enqueue) 데이터를 뺄때 front 인덱스 이동 데이터를 삭제할 경우 1. rear는 정지해 있고 2. front 는 1칸씩 이동하면서, 데이터를 추출한다.(Dequeue) 원형 큐(Circular Queue) 는 꽉 채울때.. Queue(선형 큐) 선입선출(First-In-First-Out : FIFO) : 먼저 들어간것이 먼저 나온다 Queue 이전에 배웠던, LinkedList로 구현한다. Queue 를 Array 로 개발하는 것은 상당히 비효율적이다.(특히 삭제시, 데이터를 1칸씩 앞으로 땡겨와야 한다.) => 다음 포스트에 나오겠지만, 원형 큐가 생겨나게 된 이유이다. offer : 삽입 (Enqueue) 1. 처음에 Dummy Head 와 Dummy Tail 이 한곳에 동시에 저장 되어 있다. 2. 데이터가 삽입이 이루어 지면서, Tail 노드를 뒤로 이동시킨다. poll : 추출 (Dequeue) 1. 데이터(result) 의 pointer 를 끊어낸다. = 제거 2. Head의 next pointer 를 재설정 한다. ⇒ 뒤에 쌓여 있.. Stack • 후입선출(Last-In-First-Out - LIFO) : 마지막에 들어간 것이 제일 빨리 나온다. push pop peek Double LinkedList List 의 종류 (3가지) ArrayList LinkedList Single LinkedList Double LinkedList Double LinkedList 만의 특징 1. single 방식과 달리 double 은 Node 에 Preview point 가 있다. 각 Node가 서로를 가리키고 있다. 2. Dummy Head, Dummy tail 노드를 가지고 있다. - Double LinkedList 의 처음 생성 모습 (Head 와 Tail 만 존재한다) 실제로 데이터가 들어오게 되면 아래와 같은 모양이다. Double LinkedList 의 시간복잡도 추가 : add : O(1) Single 방식에서는 맨 끝에 데이터를 추가하기 위해서는 N번 만큼 이동한 뒤에 데이터를 추가 했어야 했다. 하지만.. Single LinkedList List 의 종류 (3가지) ArrayList LinkedList Single LinkedList Double LinkedList Single LinkedList Single LinkedList 를 보통 일반적인 LinkedList라고 부른다. LinkedList는 데이터가 따로 떨어져 저장되고, 1개의 저장공간 안에서 연속을 유지하기 위해 그다음 공간의 주소를 가지고 있게 된다. 위의 그림에서 파란 네모 공간을 링크드 리스트에서는 Node 라고 한다. Node는 데이터 공간 (오른쪽 상자) Next Node Point : 다음 연결 지점, 그다음 공간의 주소를 가지고 있음 (왼쪽 상자) 그림을 통한 이해 아래의 그림은 4개의 Node를 가지는 LinkedList 이다. 맨앞의 Node : Head 맨끝.. ArrayList List 의 종류 (3가지) 1. ArrayList 2. LinkedList 2-1 Single LinkedList 2-2 Double LinkedList ArrayList는 실제 메모리 공간 상(물리적 공간)에서도 연속적으로, 데이터가 할당된다.(Array 특성과 동일) ArrayList의 생성은 다음과 같은 구문들로 가능. ArrayList integers1 = new ArrayList(); // 타입 지정 ArrayList integers2 = new ArrayList(); // 타입 생략 가능 ArrayList integers3 = new ArrayList(10); // 초기 용량(Capacity) 설정 ArrayList integers4 = new ArrayList(integers1); // 다.. Array | 배열(Array) 이란? 선형 자료구조(Data Structure)중 하나로, 동일한 타입의 연관된 데이터를 메모리에 연속적으로 저장하여 하나의 변수에 묶어서 관리하기 위한 자료 구조 Java 에서는 ??개 크기의 배열 선언하겠다고 적어줘야 함. JS, Python 은 곧바로 선언. // Java 방식 String strArray = String[10]; // 10개 짜리 String 배열을 선언 // JS 방식 var jbAry = new Array(); // Py 방식 a = [] 그림을 통해 Array를 이해해 보자. Array를 생성하면 보통 선언된 크기만큼 [메모리 = RAM]에 할당 된다. (위의 그림에서 예시로 10개 설정함) Array에서 가장 중요한 핵심개념은 랜덤엑세스(Random .. 이전 1 다음
