처음부터 차근차근

Queue 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. - wikipidia 먼저 들어간 것이 먼저 나가는 "선입선출"로, FIFO 구조를 가지고 있다. 삭제 연산이 수행되는 곳을 Front, 삽입 연산이 이루어지는 곳을 Rear로 FIFO 구조를 위해서 스텍과 다르게 큐의 한쪽 끝에는 삽입 작업이, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어지고 있다. 큐는 Rear에서 이루어지는 삽입 연산을 Enqueue라고 부르며, Front에서 이루어지는 삭제 ..

이번에는 이중 연결 리스트를 구현했다. Doublylinkedlist 구현 // 이중 연결 리스트 Class Node class Node { constructor(data) { this.data = data; this.next = null; // 이중 연결 리스트이기 때문에 이전 값도 추가되어야 한다. this.prev = null; } } class DoublyLinkedList { constructor() { // 처음 만들었을 경우, head는 null을 넣어야 한다. this.head = null; // 마지막도 null을 해준다. this.tail = null; // 연결 리스트의 크기를 보기 위해 삽입 this.length = 0; } pushFirst(data) { let newNode = ..

C++이나 Java의 경우 Linkedlist 자료구조를 지원하지만, Javascript는 그렇지 않다. (브라우저 언어라 그런지 이런게 없다니..) Node.js Backend로써 한번 자료 구조를 직접 제작해봤다. Node Class 만들기 단일 연결 리스트를 구현하기 위해서는 먼저 노드를 만들어주는 Class를 생성해야 한다. // 단일 연결 리스트 Node 제작 class class Node { constructor(data) { this.data = data; this.next = null; } } data를 입력하고 반환하는 Node 클래스를 하나 생성하였다. Linkedlist Class 만들기 class LinkedList { constructor() { // 처음 만들었을 경우, head..

Linkedlist란? 연결 리스트(Linkedlist)는 각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 데이터를 담고있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전 노드와의 연결을 담당하게 된다 - wikipidea 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조이다. 삽입과 삭제 : O(1) (삭제의 경우 특정 노드를 아는 경우에는 1이지만, 모르는 경우에는 n만큼의 시간이 소요된다.) 탐색 : O(n) 연결 리스트의 가장 첫 번째 지점을 Head라고 부른다. 마지막 노드는 Null을 가리킨다. 장단점 장점 연결 리스트는 데이터 구조의 큰 틀을 바꾸지 않고 노드를 추가하거나 삭제하기 쉽다. 연결 리스트는 배..