20210804 선형 자료구조와 비선형 자료구조
오늘은 선형 자료구조인 배열, 연결리스트, 스택, 큐, 해시테이블와 비선형 자료구조인 그래프에 대해 간단하게 정리하고자 한다. 😆
배열
배열이란?
메모리상에서 데이터가 연속적인 형태로 구성된 자료구조이다.
배열에 포함된 원소는 순서대로 인덱스를 갖는다.
배열의 특징
- 고정된 크기를 가지며 일반적으로 동적으로 크기를 늘릴 수 없다.
- 자바스크립트 같은 대부분의 스크립트 언어는 동적으로 크기가 증감되도록 만들어져 있다.
- 원하는 원소의 인덱스를 알고 있다면 O(1)로 원소를 찾을수 있다.
- 원소를 삭제하면 해당 index에 빈자리가 생긴다.
- 원소를 삭제하고 순서를 맞추는 과정 때문에 O(n)이 소요된다.
- 원소를 삽입할 때도 순서를 맞추는 과정 때문에 O(n)이 소요된다.
- 따라서 추가와 삭제가 반복되는 로직에서는 배열 사용을 권장하지 않는다.
연결리스트
연결리스트란?
요소들을 메모리에 연속적으로 배치하는 형태가 아닌 자유롭게 메모리에 할당하고 각 요소들이 다음 요소를 가리키게 하는 형태로 구현된 자료구조이다.
각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.
노드의 추가, 삭제 과정이 O(1)이 소요되므로 배열보다 추가, 삭제에서의 이점이 있다.
연결 리스트의 특징
-
메모리가 허용하는한 요소를 제한없이 추가할 수 있다.
-
탐색은 O(n)이 소요된다.
-
요소를 추가하거나 제거할 때는 O(1)이 쇼요된다.
-
Singly Linked List, Doubly Linked List, Circular Linked List가 존재한다.
-
Doubly Linked List는 각 노드가 노드의 앞과 뒤의 모든 연결정보를 갖고있다. 따라서 Singly Linked List보다 자료구조의 크기가 더 크다.
-
Circular Linked List는 Singly Linked List에서 맨 마지막 노드가 맨 앞의 노드를 가리킴으로써 순환구조의 형태를 갖는다. 순환구조 때문에 하나의 노드에서 모든 노드로 접근이 가능하다.
핵심로직
- 요소 찾기
첫 노드부터 다음 노드를 순회하면 요소를 찾기 때문에 O(n) 시간복잡도를 갖는다.
- 요소 추가
삽입할 위치의 앞뒤의 연결을 재조정하는 과정을 거친다. O(1) 시간복잡도를 갖는다.
- 요소 삭제
삭제할 요소의 앞뒤의 연결을 재조정하는 과정을 거친다. O(1) 시간복잡도를 갖는다.
자바스크립트로 연결리스트 구현
- Singly Linked List
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
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;
// 예외처리 : 노드가 하나도 없을때는 함수 종료
if (prevNode === null) return;
while (prevNode.next.value !== value) {
prevNode = prevNode.next;
}
if (prevNode.next !== null) {
prevNode.next = prevNode.next.next;
}
};
display = () => {
let currNode = this.head;
let displayString = '[';
while (currNode !== null) {
displayString += `${currNode.value}, `;
currNode = currNode.next;
}
displayString = displayString.substr(0, displayString.length - 2);
displayString += ']';
console.log(displayString);
};
}
const linkedList = new SinglyLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(5);
linkedList.display();
console.log(linkedList.find(3));
linkedList.remove(3);
linkedList.display();
linkedList.insert(linkedList.find(2), 10);
linkedList.display();
// 출력
// [1, 2, 3, 5]
// Node { value: 3, next: Node { value: 5, next: null } }
// [1, 2, 5]
// [1, 2, 10, 5]추가해야할 예외처리
find- 찾고자 하는 값이 없을 때
remove- 지우고자 하는 값이 없을 때
- Doubly Linked List
// 빠른 시일내에 구현하겠습니다.🤣- Circular Linked List
// 이것도.. 빠른 시일내에 구현할게요..😂스택
스택이란?
LIFO(Last In First Out)이라는 개념으로 마지막에 들어간 자료가 처음으로 나오는 자료이다. 프링글스 통에 감자칩을 쌓아넣고 빼는 방식을 생각하면된다.
자바스크립트에서는 Array 자료형에서 push, pop 메서드를 활용하면 스택형태로 사용할 수 있다.
const stack = [];
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack); // [1, 2, 3]
stack.pop()
console.log(stack); // [1, 2]큐
큐란?
FIFO(First In First Out)이라느 개념으로 먼저 들어간 데이터가 먼저 빠저나오는 자료구조이다.
줄서기를 생각하면된다.
주의!
보통 자바스크립트에서 큐를 사용할 때 배열과 shift 메서드를 사용하곤 한다.
하지만 이는 큐를 완전하게 사용하는것이 아니다.
원래 큐는 dequeue를 했을 때. O(1) 시간복잡도를 기대하는 것인데
배열과 shift 를 하게 될 경우 O(n) 시간복잡도를 갖게된다.
정말 제대로 된 큐를 사용할려면 구현을 해서 사용하는것이 바람직하다.
배열로 큐구현
구현이 간단하기 때문에 코딩테스트에서 사용할 때 추천한다.
class Queue {
constructor() {
this.queue = [];
this.front = 0;
this.reer = 0;
}
enqueue = value => {
this.queue[this.reer++] = value;
};
dequeue = () => {
const value = this.queue[this.front];
delete this.queue[this.front];
this.front += 1;
return value;
};
peek = () => {
return this.queue[this.front];
};
size = () => {
return this.reer - this.front;
};
display = () => {
console.log(this.queue);
};
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
console.log(queue.dequeue()); // 1
queue.enqueue(8);
console.log(queue.size()); // 3
console.log(queue.peek()); // 2
console.log(queue.dequeue()); // 2
console.log(queue.dequeue()); // 4
queue.display(); // [ <3 empty items>, 8 ]배열에 빈공간이 생기겨서 메모리 효율은 떨어질수 있을것 같다.
링크드 리스트로 큐 구현
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;
}
this.size += 1;
};
dequeue = () => {
const value = this.head.value;
this.head = this.head.next;
this.size -= 1;
return value;
};
peek = () => {
return this.head.value;
};
display = () => {
let currNode = this.head;
let displayString = '[';
while (currNode !== null) {
displayString += `${currNode.value}, `;
currNode = currNode.next;
}
displayString = displayString.substr(0, displayString.length - 2);
displayString += ']';
console.log(displayString);
};
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
queue.display();
console.log(queue.dequeue()); // 1
queue.enqueue(8);
console.log(queue.size); // 3
console.log(queue.peek()); // 2
console.log(queue.dequeue()); // 2
console.log(queue.dequeue()); // 4
queue.display();
해시테이블
해시테이블이란?
(사진출처: 위키백과)
키와 값을 저장하는 자료구조로 키를 해싱하여 나온 index에 값을 저장하는 선형 자료구조이다.
탐색, 삽입, 삭제 모두 O(1) 시간복잡도를 갖기 때문에 자료를 빠르게 접근할 때 활용할 수 있다.
해시테이블의 문제점
키를 해싱하여 나온 index가 겹치는 경우가 발생한다. 이를 해시충돌이라고 하는데 이를 해결하기 선형탐사법, 제곱탐사법, 이중해싱, 분리연결법 등의 방법을 이용해서 충돌을 해결한다.
자바스크립트에서 해시테이블은?
자바스크립트에서는 일반적으로 객체(Object), 맵(map) 자료구조를 활용하여 해시테이블로써 활용한다.
그래프
그래프란?
(사진출처: 위키백과)
정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다. 지하철 노선도를 떠올리면 된다.
그래프의 특징
- 정점은 여러 개의 간선을 가질 수 있다.
- 간선은 가중치를 가질 수 있다.
- 사이클이 발생할 수 있다.
그래프의 분류
방향에 대한 분류
방향 그래프 : 한쪽 방향으로만 이동이 가능하다.
무방향 그래프 : 양쪽 방향으로 이동이 가능하다.
연결에 대한 분류
연결 그래프 : 모든 정점이 서로 이동이 가능한 상태인 그래프
비연결 그래프 : 특정 정점쌍 사이에 간선이 존재하지 않는 그래프
완전 그래프 : 모든 정점기리 연결된 상태인 그래프
사이클 : 그래프의 정점과 간선의 부분 집한에서 순환이 되는 부분
