Data Structure

[번역] Performance of Array vs. Linked-List on Modern Computers

출처 : https://dzone.com/articles/performance-of-array-vs-linked-list-on-modern-comp Performance of Array vs. Linked-List on Modern Computers 위에서 설명했다시피 Linked-list는 특정 지점에서 Array보다 일반적으로 더 빨랐을지 모르지만, 현대 기술이 개선 된 후 배열이 더 선호되고 있다. 여기서 언급된 Array는 자동적으로 배열의 크기가 조정되는 Array (C++의 vector, Java의 ArrayList 혹은 C#의 List) 다. 물론 이론적으론... 지금까지 배운 이론적인 내용으로는 Linked-list가 Array에 비해서 random-insertion과 random-dele..

[자료구조] HashSet이란 무엇인가?

HashSet이란 무엇인가? 앞선 포스팅에서 ADT 관점에서 List와 Set의 차이점에 대해 살펴보았다. 하지만 ADT의 구현체인 DS관점에서 HashSet이 내부적으로 어떻게 구현되었는지 살펴보고자 해당 포스팅을 작성한다. Set은 '중복 원소를 허용하지 않는다'가 포인트라고 했다. 그러면 Hash는 왜 붙은 것일까? 이를 알기 위해서는 먼저 Hash에 대한 기본 개념을 알아야하기에 Hash에 대해 알아보자. 해싱이란? (Hashing) Hash, HashTable에 대한 개념은 아래 포스팅에서 자세하게 설명하였으니 참고하기 바란다. [자료구조] 해시테이블(HashTable)이란? 해싱이란? (Hashing) 해싱이란 임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값..

[자료구조] List vs Set 정의 & 차이점

Ordered collection vs Unordered collection 우선 List와 Set의 공통점으로는 "같은 종류(타입)의 데이터를 저장" 한다는 특징을 갖는다. 이에 반해 차이점은 다음과 같다. List 입력 순서를 유지하며, 데이터의 중복을 허용 인덱스를 통해 저장 데이터에 접근이 가능 Set 입력 순서를 유지하지 않으며, 데이터의 중복 허용하지 않음 데이터에 null 입력 가능하나, 한 번만 저장하고 중복 저장을 허용하지 않음 인덱스가 따로 존재하지 않기 때문에 Iterator를 사용하여 조회 위와 같이 너무 명확한 차이를 갖는 두 ADT를 살펴본 이유는 무엇일까? 단순히 면접 대비를 위해 저 짧은 개념들을 살펴볼 수도 있지만 최종적으로는 실무에서 상황에 맞는 ADT를 이용하기 위한 목..

[자료구조] 해시테이블(HashTable)이란?

해싱이란? (Hashing) 해싱이란 임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다. 위 그림에서 dog 라는 문자열을 해시함수를 이용해 새로운 값으로 변환한 것을 볼 수 있는데 이 경우엔 암호화에 쓰이는 해시 알고리즘인 MD5를 사용한 것이다. 만약 특정 길이를 32bit로 고정된다고 가정하에 아주 간략하게 보자면 다음과 같은 이미지라고 보면 된다. ※ 참고 이 때 32bit는 2진수일 때 기준이므로, 16진수로 보자면 4bit당 한 묶음이기 때문에 16진수로 표현하면 8개의 문자를 얻게 될 것이다. 즉, 해시함수를 돌리기 전 문자열의 길이가 얼마건 일정한 길이를 얻는다는 것이다. 실제로 대표적인 해시함수인 SHA계열의 SHA-512는 5..

[자료구조] 추상 자료형(Abstract Data Type, ADT)이란?

추상 자료형(Abstract Data Type, ADT)이란? 구현하고자 하는 구조에 대해 구현 방법은 명시하지 않고 자료구조의 특성들과 어떤 Operations들이 있는지를 설명하는 자료구조의 한가지 형태. 즉, 일종의 '규칙'들의 나열이라고 쉽게 이해할 수 있다. ADT의 가장 대표적 예로는 스택(Stack)과 큐(Queue)가 있다. Abstract Data Type vs Data Structure 우리가 알고 있는 자료구조(Data structure)는 추상 자료형이 정의한 연산들을 구현한 구현체를 가리킨다. 즉, 추상 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료구조와는 다르다. 예를 들어, 스택(Stack)의 형태는 LIFO 값들의 모임이고 push, pop, size 등의 연산을 정..

자바[JAVA] - Array vs ArrayList vs LinkedList 성능 비교 on Modern Computers

Array vs Linked list를 비교 Array와 Linked List의 주된 차이점들은 메모리 구조에 있다. Array는 메모리상에서 연속적으로 데이터를 저장하고, Linked List는 불연속적으로 저장한다. 메모리 구조의 차이로 인해 operation구현 방법이 다르고 시간복잡도도 다르다. 또한 메모리 활용도에서도 차이가 있다. 상황에 따라 메모리를 효율적으로 사용할 수 있는 자료구조가 달라진다는 것이다 Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조 다. Linked List는 메모리상에서는 연속적이지 않지만, 각각의 원소가 다음 원소의 메모리 주소값을 저장해 놓음으로써 논리적 연속성을 유지한다. 그래서 각 operation의 시간복잡도가 다르다. 데이터 조회는 Array의..

자바[JAVA] - Linked List 구조 & 사용법 정리

LinkedList 컬렉션 자바의 Linked List는 ArrayList와 같이 인덱스로 접근하여 조회 / 삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있다는 점이 특징이다. ArrayList는 내부적으로 배열을 이용하여 메서드로 조작이 가능하게 만든 컬렉션이라면, Linked List는 노드(객체) 끼리의 주소 포인터를 서로 가리키며 링크(참조)함으로써 이어지는 구조이다. 위 그림을 보면 LinkedList는 각기 노드마다 화살표로 연결되어 리스트 형태로 나열되어 있는 것을 볼 수 있다. 여기서 노드는 하나의 객체라고 보면된다. 즉, 객체를 만들면 객체의 주소가 생기게 되는데, 노드마다 각기 객체의 주소를 서로 참조함으로서 연결 형태를 구성하는 것이다. 즉, Linked List는 물리적인 ..

자바[JAVA] - ArrayList 구조 & 사용법 정리

ArrayList 컬렉션 자바의 컬렉션 프레임워크를 접한다면 가장 먼저 배우는 컬렉션이 ArrayList 일 것이다. 자료구조(Data Structure) 이라고 해서 무언가 방대하게 느껴져 접근이 어려울 것 처럼 느끼겠지만, ArrayList는 배열의 상위호환 버전 정도로 이해하면 된다. 기존의 배열만으로는 자료를 담고 관리하는데 약간 불편함이 있어서 나온 것이 ArrayList 이기 때문이다. ArrayList 특징 연속적인 데이터의 리스트 (데이터는 연속적으로 리스트에 들어있어야 하며 중간에 빈공간이 있으면 안된다) ArrayList 클래스는 내부적으로 Object[] 배열을 이용하여 요소를 저장 배열을 이용하기 때문에 인덱스를 이용해 요소에 빠르게 접근할 수 있다. (시간복잡도 : O(1) ) 크..

자바[JAVA] - 스택(Stack)

Stack 자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'라는 의미를 갖고 있다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있다. Stack은 '마지막에 추가된 데이터가 가장 먼저 나오는' 특징을 가지고 있는 후입선출 LIFO(Last In First Out)의 자료구조다. 시간복잡도는 push O(1) , pop O(1) 이다. 활용 예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS) 등이 있다. 스택의 입출력은 맨 위에서만 일어나기 때문에 스택의 중간에서는 데이터를 삭제하는 것이 불가능 하다 스택이 입출력이 이루어지는 부분을 스택 상단(Stack top) , 바닥 부분을 스택 하단(Stack bottom) ..

자바[JAVA] - 배열(Array)

배열 자료형 배열은 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조 이다. 배열은 하나의 블록안에 여러 데이터들을 모아 집합시켜 저장함으로써 데이터를 구조적으로 다루는 것을 돕는다. 배열을 구성하는 각각의 값을 배열 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자를 인덱스(index)라고 칭한다. 배열의 특징 고정된 저장 공간(fixed-size) 순차적인 데이터 저장(order) Array의 장점은 lookup과 append가 빠르다는 것이다. 따라서 조회를 자주 해야되는 작업에서는 Array 자료구조를 많이 사용한다. Array의 단점은 fixed-size 특성상 선언 시에 Array의 크기를 미리 정해야 된다는 것이다. 이는 메모리 낭비나 추..