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

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

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

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

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