단순 구조
정수, 실수, 문자열, 논리 자료형 같은 것들입니다.
선형 구조
한 원소 뒤에 하나의 원소만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 가집니다.
배열(순차 리스트)
일반적으로 변수를 선언하면 메모리 상에 데이터가 기록되게 됩니다. 우리는 변수를 통해 기록된 데이터를 꺼내 쓸 수 있습니다. 연관된 데이터를 쓰기 위해서는 여러개의 변수를 선언하는 방법이 있지만 보통 이렇게 작성을 하지는 않습니다. 이런 상황에서는 배열을 사용하게 됩니다.
배열은 연관된 데이터를 연속적인 형태로 구성된 구조를 가집니다. 배열에 포함된 원소는 순서대로 index를 가지며, index를 사용해 조회하거나 데이터를 수정할 수 있습니다.
원하는 원소의 index를 알고 있다면 O(1)로 원소를 찾을 수 있습니다.
원소를 삭제하면 해당 index는 빈자리가 생깁니다. 배열의 요소를 삭제하면 단순히 공백으로 두는 경우도 있지만, 후의 정렬이나 탐색을 위해 앞당겨야 하는 경우도 있습니다. 삭제 후 순서를 맞추려면 O(n)이 소요됩니다.
반대로, 요소를 중간에 추가할 때로 삭제 로직과 비슷합니다. 마찬가지로 O(n)이 소요됩니다.
따라서 추가와 삭제가 반복되는 로직이라면 배열 사용을 권장하지 않습니다.
연결 리스트
추가와 삭제가 반복되는 로직이라면 연결 리스트를 사용하는 것이 좋습니다.
연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조입니다. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성됩니다.
배열과는 다르게 메모리가 허용하는 한 요소를 제한없이 추가할 수 있으며 탐색에는 **O(n)**이 소요됩니다. 요소를 추가하거나 제거할 때는 **O(1)**이 소요됩니다. 연결 리스트에는 Single Linked List, Double Linked List, Circular Linked List가 있습니다.
배열은 순차적 데이터가 들어가기 떄문에 메모리 영역을 연속적으로 사용하지만 연결리스트는 순차적으로 사용하지 않고 메모리가 퍼져있으며, 각 메모리 영역을 알기 위해 포인터로 각 영역을 참조합니다.
연결 리스트에서 요소를 탐색하기 위해서는 헤드 포인터에서 시작합니다. 다음 요소인 헤드를 찾고, 해당 요소가 우리가 찾는 요소인지 확인하고 아니라면 포인터 영역을 참고하여 다음 요소를 확인하는 방식을 계속해서 반복하게 됩니다.
연결 리스트에서는 삭제할 요소를 찾아 삭제할 요소를 가리키는 이전 요소가 가리키는 포인터를 삭제할 요소의 다음 요소에 연결합니다. 그 이후 삭제할 요소를 삭제해주면 삭제가 완료됩니다.
요소를 추가할 때는 추가할 요소의 포인터를 끼워넣을 부분의 다음 요소를 가리키게 만들고 끼워넣을 영역 이전 영역의 포인터를 추가할 요소를 가리키도록 수정합니다.
07
- Single Linked List(단일 연결 리스트) 가장 기본적이고 단순한 형태의 연결 리스트입니다. 단순히 Head에서 Tail까지 단방향으로 이어지는 연결 리스트입니다. 여기서 Head는 가장 첫 번째 요소를 말하고 Tail은 가장 마지막 요소를 말합니다. 헤드 포인터는 헤드를 가리키는 가장 첫 번째 출발점이라고 할 수 있습니다. Tail 요소는 포인터 영역이 null 입니다. 즉, 포인터 영역이 null이면 더 이상 갈 곳이 없다는 의미이기에 연결 리스트의 끝이라고 말할 수 있습니다.
- Double Linked List(이중 연결 리스트) 이중 연결 리스트는 단일 연결 리스트와는 다르게 포인터를 두 개 가지고 있습니다. 다음과 이전을 가리고 있어 양방향으로 이어진 구조를 가지고 있습니다. 포인터 변수가 하나 추가되기 떄문에 단일 연결 리스트보다 자료 구조의 크기가 조금 더 크다는 단점이 있습니다. 이중 연결 리스트에서 요소를 추가하기 위해서는
- 추가할 요소의 다음을 추가할 위치의 다음 요소를 가리키게 만들어줍니다.
- 이전 요소의 다음을 추가할 요소의 데이터 영역을 가리키도록 만듭니다.
- 다음 요소의 이전을 추가할 요소를 가리키게 합니다.
- 추가할 요소의 이전을 이전 요소를 가리키게 만들어 줍니다. 요소를 삭제하기 위해서는
- 삭제할 요소의 이전 요소의 다음을 삭제할 요소의 다음을 가리키게 합니다.
- 삭제할 요소의 다음 요소의 이전을 삭제할 요소의 이전을 가리키게 합니다.
- 마지막으로 삭제할 요소를 삭제해줍니다. 요소의 추가, 삭제 둘 다 **O(1)**이 소요됩니다.
- Circular Linked List(원형 연결 리스트) single 혹은 double linked list에서 tail이 head로 연결되는 연결 리스트입니다. 메모리를 아껴쓸 수 있으며 원형 큐 등을 만들 때 사용합니다. 중간에서 시작하더라도 한 바퀴를 모두 탐색할 수 있습니다.
/* single linked list 코드로 구현해보기 */
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}
class SingleLinkedList {
constructor(){
this.head = null;
this.tail = null;
}
// 탐색
find(value){
let currNode = this.head;
while(currNode.value !== value){
currNode = currNode.next;
}
return currNode;
}
// 추가
append(newValue){
const newNode = new Node(newValue);
if(this.head === null){
this.head = newNode;
this.tail = newNode;
}else{
this.tail.next = newNode;
this.tail = newNode;
}
}
// 중간에 추가
insert(node, newValue){
const newNode = new Node(newValue);
newNode.next = node.next;
node.next =newNode;
}
// 삭제
remove(value){
let prevNode = this.head;
while(prevNode.next.value !== value){
prevNode = prevNode.next;
}
if(prevNode.next !== null){
prevNode.next = prevNode.next.next;
}
}
}
코딩 테스트에서 linked list를 직접 구현하여 사용하는 경우는 많지 않습니다. 그래서 외워둘 필요는 없지만 한 번쯤은 직접 타이핑하고 이해해보시는 것을 추천드립니다.
스택
Last In First Out 이라는 개념을 가진 선형 자료구조입니다. 바닥이 막힌 상자를 생각하시면 됩니다. 여기에 요소를 넣는 것을 push 빼는 것을 pop 가장 위에 있는 데이터를 top이라고 합니다.
스택의 동작 원리는 굉장히 단순합니다. 요소를 넣는 push와 요소를 넣는 pop만 존재합니다. 가장 위에 있는 요소만 조작하기에 구현도 어렵지 않습니다.
스택 자료구조를 사용하는 가장 대표적인 것은 스택 메모리 입니다. 스택 메모리는 함수가 호출되면 생성되는 지역 변수, 매개 변수가 저장되는 메모리 영역입니다.
// 1. sum 함수 실행: 매개 변수와 지역 변수, 반환 주소값 push
function sum(a,b){
return a+b;
}
// 값이 반환되면 pop
// 2. print 함수 실행: 지역 변수, 매개 변수, 반환 주소값 push
function print(value){
// 3. console.log() 실행: 지연 변수, 반환 주소값, 매개 변수 push
console.log(value);
// 로그 출력을 마치면 pop
}
// 함수 호출 완료로 pop
print(sum(5,10))
- Array push를 하면 배열의 첫번째부터 순차적으로 요소가 삽입되며, pop을 하면 가장 마지막 요소를 삭제합니다. 이러한 방식은 배열의 단점인 중간 요소 추가, 삭제 로직을 사용하지 않기 때문에 배열 사용 시 유리한 방식입니다.
const stach = []
// push
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack); // [1,2,3]
// pop
stack.pop();
console.log(stack); // [1,2]
// Get Top
console.log(stack.at(-1)); // 2
- Linked List C언어나 Java 같은 경우 stack의 크기가 고정되지 않는 경우 크기가 유한한 배열 대신, linked list로 구현하는 경우가 많았습니다. 이 경우, linked list의 head가 stack의 top이 됩니다.
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}
class SingleLinkedList {
constructor(){
this.head = null;
this.size = 0;
}
push(value){
const node = new Node(value);
node.next = this.top;
this.top = node;
this.size += 1;
}
pop(){
const value = this.top.value;
this.top = this.top.next;
this.size -= 1;
return value;
}
size(){
return this.size;
}
}
큐
First In First Out이라는 개념을 가진 선형 자료구조입니다. 먼저 들어간 것이 먼저 나오고, 나중에 들어간 것이 나중에 나오는 개념입니다. Queue의 맨 앞을 Front라고 부르며 맨 마지막을 Rear라고 부르며 큐에 요소를 추가하는것을 EnQueue, 빼는 것을 DeQueue라고 부릅니다.
- 선형 큐(Linear Queue)
- Array
배열에서 선형 큐를 사용하기 위해서는 먼저 들어간 요소가 먼저 빠져나와야 하므로 앞으로 우선 들어간 요소가 빠져나오며 그 이후로 들어가는 요소들은 계속해서 뒤에 붙어들어가게 됩니다. - linked list linked list의 Head가 Front, Tail이 Rear가 됩니다. linked list를 사용하면 배열과는 다르게 index에 대한 고민은 하지 않아도 됩니다.
- Array
// Linear Queue: Array
class Queue {
constructor(){
this.queue = [];
this.front = 0;
this.rear = 0;
}
enqueue(value){
this.queue[this.rear++] = value;
}
dequeue(){
const value = this.queue[this.front];
delete this.queue[this.front];
this.front++;
return value;
}
peek(){
return this.queue[this.front];
}
size(){
return this.rear - this.front;
}
// Linear Queue: linked list
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}
class Queue {
constructor(){
this.head = null;
this.tail = null;
this.size = 0;
}
enQueue(newValue){
const newNode = new Node(newValue);
if(this.head === null){
this.head = this.tail = newNode;
}else{
this.tail.next = newNode;
this.tail = newNode;
}
}
deQueue(){
const value = this.head.value;
this.head = this.head.next;
this.size--;
return value;
}
peek(){
return this.head.value;
}
}- 간혹 shift() 함수로 구현하는 경우가 있는데 자바스크립트 배열에서 shift()는 선형 시간이 걸리기 때문에 Queue에서 기대하는 로직이 수행되지 않습니다. 때문에 Shift()는 사용하지 않고 구현하는 것이 좋습니다.
- 원형 큐(Circular Queue) Front와 Rear가 이어져있는 Queue입니다. 한정된 공간을 효율적으로 이용하기 위해 사용하는 자료구조이기 떄문에 linked list로 구현했을 때 이점이 없습니다.
// Array
class Queue {
constructor(maxSize){
this.maxSize = maxSize;
this.queue = [];
this.front = 0;
this.rear = 0;
this.size = 0;
}
enqueue(value){
if(this.isFull()){
console.log("Queue is full.")
return;
}
this.queue[this.rear] = value;
this.rear = (this.rear + 1) % this.maxSize;
this.size++;
}
dequeue(){
const value = this.queue[this.front];
delete this.queue[this.front];
this.front = (this.front + 1) & this.maxSize;
size--;
return value;
}
isFull(){
return this.size === this.maxSize;
}
peek(){
return this.queue[this.front];
}
해시
해시 테이블은 키와 값을 받아 키를 해싱하여 나온 index에 값을 저장하는 선형 자료구조 입니다. 삽입은 **O(1)**이며 키를 알고있다면 삭제, 탐색도 **O(1)**로 수행됩니다.
해시 함수는 입력받은 값을 특정 범위 내 숫자로 변경하는 함수입니다. 해시 함수는 특정 구현 방법이 있지는 않습니다. 따라서 우리 마음대로 구현해도 됩니다.
이렇게 해시 함수를 이용한 해시 테이블은 완벽해 보이지만 문제점이 있습니다. 해시 함수의 결과가 동일한 결과가 발생할 수 있다는 것인데, 이것을 해시 충돌이라고 부릅니다.
해시 충돌을 해결하기 위한 방법에는 4가지가 있습니다.
- 선형 탐사법: 충돌이 발생하면 옆으로 한 칸 이동하는 것입니다. 단순하지만 특정 영역에 데이터가 몰릴 수 있다는 단점이 있으며, 이동한 버킷에서 또 충돌이 발생한다면 충돌이 발생하지 않을 때까지 이동합니다. 때문에 충돌을 해결하는데 최악의 경우 선형시간(O(n))이 걸릴 수 있습니다.
- 제곱 탐사법: 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동합니다. 충돌이 발생할수록 범위가 커지기 때문에 데이터가 몰리는 선형 탐사법의 단점을 보완할 수 있습니다.
- 이중 해싱: 충돌이 발생하면 다른 해시 함수를 이용합니다. 또 충돌이 발생하면, 충돌이 발생하지 않을 때까지 다른 해시 함수로 계속해서 새로운 인덱스를 생성합니다.
- 분리 연결법: 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가합니다. 대신, 이 방법은 최악의 경우 하나의 버킷이 무한정 늘어날 수 있다는 단점이 있습니다.
해시를 구현하는 방법에는 여러가지가 있습니다. 자바스크립트에서는 배열도 객체 타입이기 때문에 배열로도 만들 수 있지만, 권장하지는 않습니다.
- 객체: 보통 많이 사용하는 가장 간단한 방법은 객체로 구현하는 방법입니다.
const table = {};
table["key"] = 100; // 삽입
table["key2"] = "Hello";
delete table["Key"]; // 삭제
- Map: 별도로 Map객체를 사용할 수도 있습니다. Map은 set함수를 사용해서 값을 넣고 get함수로 값을 찾을 수 있습니다. 기존 객체와는 다르게 키 값으로 Object나 배열 같은 복잡한 타입도 키로 사용할 수 있습니다. 객체의 경우 들어오는 값이 정수가 아닌 경우 전부 문자열로 바꾸기 때문에 다양한 타입의 키를 사용하고 싶다면 Map을 사용하는 것이 좋습니다. 그리고, 여러 편한 메서드를 제공하며 순회를 편하게 할 수 있습니다.
const table = new Map();
table.set("key", 100); // 삽입
table.set("key2", "Hello");
const object = {a: 1};
table.set(object, "A1"); // 객체를 키로 삽입
table.delete(object); // 삭제
table.clear(); // Map 객체 비우기
table.values(); // {}
- Set: 키와 값이 동일하게 저장됩니다. 따라서 중복된 내용을 제거해줄 때 사용할 수 있습니다.
const table = new set();
table.add("key"); // key와 value를 동일하게 삽입
table.add("key2");
table.has("key"); // 조회: true;
table.delete("key2");
table.size; // 1
table.clear();
table.size; // 0
'DataScience > Data Structure' 카테고리의 다른 글
| 알고리즘 - 정렬 (0) | 2022.12.19 |
|---|---|
| 알고리즘 - 이진탐색 (0) | 2022.12.19 |
| 알고리즘 - 시간복잡도 (0) | 2022.12.19 |
| 자료구조 - 비선형 자료구조 (0) | 2022.12.15 |
| 자료구조와 알고리즘을 공부해야 하는 이유? 자바스크립트 똑똑하게 쓰기! (0) | 2022.12.06 |