190918 data structure - 1
배열
Array는 list와 비슷한 object이며, array객체는 Array를 상속받아 생성되기 때문에, Array.protoype에 존재하는 메소드들을 사용가능하다.
메소드는 아래 주소 참고..
ex) Array.prototype.find() → arr.find()
js에서 배열의 길이와 element의 자료형은 고정되어 있지 않다. 여러가지 다 넣을 수 있음.
js배열은 밀집도가 정형화 되어있지 않다. 필요시 typed array를 사용. 혹은 List 추상 클래스를 이용해 사용.
배열은 인덱스로 무조건 정수만 허용됩니다.
Array object를 extends하여 생성된다.
권장되는 방식은 new를 이용하는 것이 아닌
var array = []; // 이러한 방식으로 편하게. 빈 array를 만든다
var fruits = ['Apple', 'Banana']; // array생성과 동시에 element를 채운다
var first = fruits[0]; // access element by index// 인덱스로 호출하여 element 변경이 가능하다.
var arr = [‘가’,’나’,’다’]
arr[0] = ‘나’
arr
[“나”, “나”, “다”]
리스트
Array객체에서 index 기능을 빼고, 빼곡히 순차적으로 저장하고, 빈엘레먼트 허용x → 빈틈없는 데이터적재가능.
array는 value가 삭제하면 index는 남는 메모리 낭비 존재.
var List = function(){
this.dataStore = [];
this.pos = 0;
this.listSize = 0;
}
// List 추상객체 역할을 할 function 구현아래와 같이 필요한 function을 prototype단계에서 직접 정의해서 사용.
List.prototype.append = function(element){ this.dataStore[this.listSize] = element;
this.listSize++; }출처
스택
위 사진을 떠올리면 도움이 된다.
영어로는 LIFO(Last In First Out)이다.
말그대로 마지막에 들어간(push) 것이 가장 먼저 출력(pop)된다.
let stack = []; 케이스 만들고
stack.push('a'); push
stack // ['a']
stack.push('b'); push
stack // ['a','b']
stack.pop() = 'b' // 제일 뒤에꺼 pop. return으로 해당 값이 나온다.
stack // [a]우리는 이 stack을 js를 사용하면 항상 사용하고 있는데,
바로 함수의 callstack이 그 예이다.
너무 잘 표현된 gif가 있어서 가져와 보았다. (출처는 gif하단 링크)
펑션이 실행되기전에 callstack에 차례대로 쌓이고, 내부의 펑션부터 차례대로 pop되며 실행이 된다.
큐
큐는 우리가 늘 어디서나 서는 ‘줄’을 추상화 한 개념이다.
먼저 온 사람이 먼저 밥을 먹을 수 있는 뭐 그런…
‘큐’를 잡는다는 말 자체도 이미 롤을 해본 사람이라면 알 것이다.
‘큐를 잡는다’라는 것은 게임 하기 위한 대기열에 내 순번을 발급받고, 대기하는 것이다.
이 경우는 FIFO(First In First Out) 이다.
es6의 class를 이용해 Queue클래스를 만들어보면,
class Queue {
constructor() {
this._arr = [];
}
enqueue(item) {
this._arr.push(item);
}
dequeue() {
return this._arr.shift();
}
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue(); // 1queue에 넣는 것은 push. 뒤에서 부터 순서대로 넣는다.
queue에서 빼는 것은 shift(). 가장 앞에 있는 element를 return한다.
연결리스트
[a,b,c,e,f,g……z]라는 array(arrayList) 가 있고, c와 e사이에 d를 넣어보자.
e부터 z까지의 의 인덱스를 순서대로 하나씩 밀어서 저장하는 작업이 필요하다.
이러한 낭비를 연결리스트는 해결할 수 있다.
연결리스트는
노드(node = element)의 집합이며
node는
실제 자료를 담고 있는 data field와
다음 노드의 위치정보를 담고있는 link field로 구성된다.
앞서 array(arrayList)에서 array중간에 값을 추가하는 경우에 넣으려는 자리 이후의 모든 element의 index를 변경해줘야 했다.
그러나 linkedList의 경우는 아래와 같다.
먼저 첫번째 node, head를 호출해 첫번째 노드를 찾는다. (15)
해당 위치부터 순서대로 .next()를 통해 value를 23으로 갖는 node의 전 node까지 value를 통해 접근한다. ( 물론 6이라는 value는 알고 있어야 가능하다.)
넣을 자리 앞의 node를 찾았다면, 6 다음의 node를 temporary variable에 저장을 먼저 해주고,
90이라는 value를 갖는 node를 생성, 6node.next에 생성한 90node를 지정합니다.
그리고 임시저장해두었던 temp node23을 90node.next에 지정해주고,
temp node23.next 에 4node를 지정해줍니다.
js기준으로 보면
아래와 같다.
const LinkedList = (() => { // 노드를 담고, head를 기억하는 linkedList.
class LinkedList {
constructor() {
this.length = 0;
this.head = null;
}
}
class Node {
constructor(data) {
this.data = data; // node의 value부분
this.next = null; // 다음 node를 연결하는 link부분.
}
}
return LinkedList;
})();
앞에서 말로 표현해보았던 추가의 경우.
add(value) {
const node = new Node(value);
let current = this.head;
if (!current) {
this.head = node;
this.length++;
return node;
} else {
while(current.next) {
current = current.next;
}
current.next = node;
this.length++;
return node;
}출처
집합
자바스크립트 집합 연산 참고.
아규먼트로 들어오는 파라미터의 value를 key로 갖는 temp{}에 적재,
temp{}에 해당 key로 값이 존재하는지로 중복 체크.
function union(a, b) {
var tmp={}, res=[];
for(var i=0;i<a.length;i++){ tmp[a[i]]=1;console.log(tmp)}
for(var i=0;i<b.length;i++){ tmp[b[i]]=1;console.log(tmp)}
for(var k in tmp) res.push(k); //해당 key를 갖는 element없는경우 추가.
return res;
}합집합 연산 log는 이렇게 된다.
