자바스크립트 자료구조 연결 리스트

(Linked List)

• 중북된 데이터의 저장을 막지 않으며 나란히 저장함.

• 선형리스트(Linear List): 배열을 기반으로 구현된 리스트

  • 간단함. 기본으로 내장되있음.
  • 데이터 타입을 연속적으로 저장
  • 장점: 간단하고 참조가 쉽다. 인덱스 값만 알면 참조가 가능하다.
  • 단점: 크기가 초기에 고정되어야 하고 변경이 불가능하다. (자바스크립트 제외). 처음이나 중간에 element를 넣으려면 번거롭다.

• 연결리스트(Linked List): 노드의 연결로 구현된 리스트

  • Element들을 차례대로 저장하지만 연속적으로 위치하지는 않는다.
  • 연속적인 항목이 포인터로 연결된다.
  • 마지막 element는 null을 가리킨다.
  • 프로그램이 실행되는 동안 크기가 바뀌고 메모리가 허용하는 용량에 따라 필요만큼 길이가 바뀔 수 있다.
  • 메모리 공간을 낭비하지 않는다. (Additional memory for pointers)
  • 장단점: 데이터의 추가/삭제가 용이하나 인덱스가 없어 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없다. 탐색 속도가 더 걸린다.

​ 탐색/정렬을 위해서는 배열을 추가/삭제를 위해서는 연결 리스트를 사용

Types of Linked List

• Simple Linked List: Item navigation is forward only
• Doubly Linked List: Items can be navigated forward and backward.
• Circular Linked List: Last item contains link of the first element as next and the first element has a link to the last element as previous...like a circle!

노드(Node)

• 연결리스트에서는 원소 사이에 서로를 연결해주는, 다음 원소를 가리키는 포인터가 포함된 노드(Node)로 구성된다.
• 연결리스트에 마지막은 Null 로 이어져있다.

연결리스트의 ADT(Method라고 봐도 무방)

• append(data): 리스트에 맨끝에 데이터 추가
• removeAt(위치): 위치에 있는 데이터 삭제
• indexOf(데이터): 데이터의 index를 반환. 존재하지 않을 경우 -1
• remove(데이터): 데이터 삭제
• insert(위치, 데이터): 위치에 데이터 삽입
• isEmpty(): 데이터가 아예 없으면 true, 있으면 false
• size():데이터 개수 반환
• contains(): 데이터가 있는지 없는지 반환

선형구조는 자료를 저장하고 꺼내는 것에 초점 vs 비선형 구조는 표현에 초점

Implement a linkedList class, in functional style, with the following properties:

• .head property, a linkedListNode instance
• .tail property, a linkedListNode instance
• .addToTail() method, takes a value and adds it to the end of the list
• .removeHead() method, removes the first node from the list and returns its value
• .contains() method, returns boolean reflecting whether or not the passed-in value is in the linked list
• Check if you can find which is the time complexity of the above functions.

1. addToTail:
   • head의 값이 null 이라면, Node의 함수를 통과해 만들어진 node 객체가 list.head와 list.tail의 값이 된다.
   • 이후 부터 들어오는 node 객체는, node.next 값만 list.head.next값으로만 새로 할당하고 list.tail값은 node로 바꿔준다.
2. removeHead:
   • 만약 list의 값이 하나라면 그냥 그 하나 객체의 value값을 반환한다.
   • 2개 이상일 경우, 변수를 만들어 일단 Head의 Value값을 할당해 준다. 그리고 새로운 Head의 Value 값으로 Tail.next.Value의 값을 할당해준다.
3. Contains:
   • While Loop을 돌려 list.tail.next에 찾는 값이 있는지 확인.

자바스크립트 자료구조 그래프 (비선형구조)

• 그래프 자료구조는 많은 알고리즘에서 사용하는 자료구조이다.
• 노드(vertex)와 엣지(arc)로 구성되어 있는데 노드는 꼭지점, 엣지는 그 점들을 이어주는 선이라고 생각하면 된다.
• 그래프는 방향성을 띄고 있으면 방향그래프, 방향성이 없다면 무방향 그래프로 나눈다. 방향그래프일경우 다른 vertex에서 오는 arc의 개수를 In-degree, 다른 vertex로 가는 arc의 개수를 out-degree 라고 부른다.

모든 버텍스가 아크로 연결된 그래프는 완전 그래프라고 하고 부분집합은 부분 그래프라고 부른다.

만약 다른 버텍스로 갈 때 하나의 아크 만으로 갈 수 있다면 근접(adjacent)하다고 한다.

그래프는 인접행렬(Adjacency Matrix) 또는 인접리스트(Adjacency List)로 표현할 수 있다.

Method

• .addNode(): adds a new node to the graph
• .contains(): checks if the node is in the graph (boolean)
• .removeNode(): removes node if present
• .addEdge(): creates an edge (connection) between two nodes if both are present
• .hasEdge(): checks if two nodes are connected
• .removeEdge(): removes the connection between two nodes
• .forEachNode(): implement function for each node

참조 - https://www.zerocho.com/category/Algorithm/post/584b9033580277001862f16c

자료구조 트리 (Tree) (비선형구조)

• 트리구조도 그래프와 같이 데이터들을 순차적으로 나열하지 않고 계층적(혹은 망)으로 구성되어 있는 비선형 구조이다.
• 트리의 예는 족보, 아니면 조직도가 있다.
• 회로(cycle)가 존재하지 않아서 가는 방향이 하나이다.

용어

• Root Node: 트리구조 최상위에 존재하는 노드
• Node: 트리를 이루는 요소
• Edge: 트리의 노드들을 연결하는 선
• Terminal Node(Leaf Node): 자신 밑에 아무런 노드가 없는 노드
• Sub-Tree: 전체적인 큰 트리 안에 들어 있는 작은 트리
• Level: 트리의 각 층. 숫자로 표현
• Height: 트리의 최고 레벨. 가장 위 층 숫자.

Method

• .addChild(): add node as a child of tree
• .contains(): checks if the node is in there or not

Binary Tree (이진트리)

• 이진트리는 자식노드가 최대 두 개인 노드들로 구성된 트리.
• 정이진트리,(full binary tree) 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree)가 대표적인 타입이다.

1. 정이진트리(full binary tree)

   • 정이진트리(full binary tree)는 모든 레벨에서 노드들이 꽉 차있는, terminal node를 제외하고는 다 자식이 있는 트리이다.
   • 
   • 노드의 개수는 n이 레벨일 때 (2^n) - 1 이다.

2. 완전이진트리(complete binary tree)

   • 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리

     

   • 높이가 n일 때 완전이진트리의 노드 개수는 2^(n-1) 보다 크거나 같고 (2^n) -1 보다 작거나 같다.

3. 균형이진트리(Balanced binary tree)
   참조 - https://lovelyseoul.tistory.com/20

   • 좌우의 높이 차가 같은 이진트리.

     

     

   Methods

   • .children property, an array containing a number of subtrees
   • .addChild() method, takes any value, sets that as the target of a node, and adds that node as a child of the tree
   • A .contains() method, takes any input and returns a boolean reflecting whether it can be found as the value of the target node or any descendant node
   • Check if you can find which is the time complexity of the above functions?
   1. 함수로 정보를 포함한 객체를 만들어서 배열에다가 push에서 정리해준다.
   2. contains는 재귀로 계속 룹을 돌려 찾아내려고 한다.

Binary Search Tree
참조 - [https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/](https://ratsgo.github.io/data structure&algorithm/2017/10/21/tree/)

• 이진검색트리는 트리 구조를 이용해 각 노드 방문으로 자료를 탐색가능하게 하는 이진 트리 자료구조이다.
  

  Tree 탐색

  • 탐색을 할 때 트리 왼쪽은 더 작은 값, 오른쪽은 더 큰 값이다. 왼쪽에 있는 2, 4, 5의 값은 1 보다 작고 오른쪽은 더 크다.

    Tree Traversal(트리순회)

  1. 전위순회 (Preorder)

     • 루트 노드에서 시작에서 노드-왼쪽 서브트리-오른쪽 서브트리로 순회. 깊이우선순회라고도 한다. (depth-first traversal)
       1, 2, 4, 5, 3

  2. 중위순회 (inorder)

     • 터미널 노드에서 시작해 노드-부모 노드-오른쪽 자식 노드로 순회. 대칭순회(Symmetric traversal)라고도 한다.

       4, 2, 5, 1, 3

  3. 후위순회(postorder)

     • 터미널노드에서 시작해 자식 노드를 다 돌고 부모 노드로 넘어간다. 왼쪽부터 시작.
       4, 5, 2, 3, 1

  Method

  • .insert(): accepts a value and places in the correct position
  • .contains(): checks if the value is present
  • .depthFirstLog(): accepts a callback function and execute on every value in tree

Hash Table

• A data structure that maintains associations between two data values. Data values being associated are referred to as key and value. Has other names like Associative Array, Dictionary, Map or Hash

• 두가지 데이터를 연결해줌. Key 1개와 Value 1개가 연관되어 있어 키로 값을 구할 수 있다.

• Typical usage of arrays is in the form of a tuble, which is a data structure where each position has specific meaning and each instance are categorized accordingly. Index:Value?

• Hash Table is similar to Javascript Object. Objects are implemented using hash table.

Top Level array: storage

Index that contains key/value pairs have array called buckets.

Key/value pairs are stored in tuple array. index 0 is key and index 1 is value.

단점:

• 순서가 있는 배열에는 어울리지 않는다.
  • 순서와 상관없이 key만 가지고 hash 를 찾아 저장
• 공간 효율성이 떨어진다.
  • 저장공간 확보가 필요
• Hash Function 의 의존도가 높다.
  • 해쉬 함수에 따라 시간 효율성이 바뀐다.

Method

• Insert(): Add Data

• Retrieve(): Get Data

• Remove(): Remove Data

• Can use array, but key would be numerical. Using string would be more user-friendly.

• JS objects are implemented using hash tables, so we can't use an object to implement a hash table...?

Hasing Function

• Only return numbers that are within the array bounds (0 to length -1)
• Always output the same index value for a given input string and length.
• Maintain no memory of previous index or string.

Transmorgifier. If we put an input in, a numer comes out. then by the number, the output will come out. Constant in, constant out.

Problem: Collision. What if inputs have same index?

A: Instead of storing a single value at this idnex, store an array of values. However, then we cannot specify which is which. To solve this, store both the key and value. Introduce another array.

• Separate Chaining: If collision occurs in bucket, chain existing value with the new one. Implement linked list.

  • 장점:
    • 한정된 저장소(Bucket)을 효율적으로 사용.
    • 해쉬 함수 선택의 중요성이 감소
    • 상대적으로 적은 메모리 사용.
  • 단점:
    • 한 Hash 에 계속 연결되면 검색 효율 감소.
    • 외부 저장공간 사용, 추가 작업 필요.

• Open Addressing: 개방주소법은 hash를 건들지 않았던 chaining과는 달리 비어있는 hash를 찾아 저장한다. 여기서 비어있는 hash를 찾는 과정은 동일해야 함.

  • 선형 탐색(Linear Probing): 다음이나 n개의 해쉬를 건너뛰고 저장.
  • 제곱 탐색(Quadratic Probing): Collison이 있던 Hash의 제곱을 한 Hash에 데이터 저장.
  • 이중해시(Double Hashing): 다른 해시함수를 한번 더 적용한 해시에 데이터 저장
  • 장점:
    • 또 다른 저장공간 없이 해시테이블 내에서 처리할 수 있음.
    • 다른 저장공간을 위한 작업을 안해도 됌.
  • 단점:
    • 해시 함수의 성능에 의해 전체 테이블의 성능이 결정
    • 데이터의 길이가 늘어나면 그 용량에 맞는 저장소를 마련(Resizing)

Hash Table Resizing

• Hash tables operate most effectively when the ratio of tuple count to storage array length is between 25% and 75%.

• When the ratio is

  • Greater than 75%, double the size of the storage array

  • less than 25%, half the size of the storage array

  • Resizing means you need to rehash every key because it may end up in different bucket. Hasing function depends on the storage array size. Maintain time constant!

  Worst Scenario:

  • Most of the time, time insert & remove operations have O(1) of Big-O notation. However, O(n) can happen when...
    • Hash table is growing, it resizes itself and every element must be rehashed.
    • All keys can possibilly hash to the same bucket, which becomes a O(n) search for an item.
  • Quality of hashing algorithm is a major factor that determines how tuples will be distributed within buckets.
    • An algorithm with more entropy will produce superior result. I guess this means having more randomness increase probability of giving you the result you want..?

참조 - https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o