[Udemy 자료구조]클래스, 싱글 연결 리스트

1. 클래스

a. 개념

        i. 사전에 정의된 속성 및 메소드들을 이용해 객체를 생성하기 위한 청사진
        ii. 엄격하게 보면 자바스크립트가 클래스를 지원하는 것은 아니다. 자바스크립트에 이미 존재하는 프로토타입 기반 상속자들을 구문적으로 눈속임한 것.

b. 인스턴스

        i. 클래스 생성자함수로 생성된 객체. Array 생성자함수로 생성된 배열 또한 인스턴스다.

c. 클래스 메서드

        i. static : 클래스에 종속되는 반면 클래스의 개별 인스턴스 메서드에는 종속적이지 않은 메서드를 생성할 때 사용한다. 한마디로, 인스턴스 없이 호출되는 메서드다.

d. 클래스에서의 this

        i. 클래스로부터 생성된 객체, 즉 실제 인스턴스를 참조한다.

2. 싱글 연결 리스트(단일방향 연결리스트)

a. 개념

        i. what is linked list?(연결 리스트란 무엇인가)
        - 문자열, 숫자 등 원하는 데이터를 저장하는 자료 구조. 배열처럼 순서가 있다.
        - 배열과의 차이점은, 배열은 데이터마다 해당 위치의 인덱스가 부여된다. 연결리스트는 인덱스 없이 데이터들을 저장한다. 5번째 데이터에 접근하려면 첫번째부터 다 거쳐서 5번째까지 가야하며, 곧장 5번째 데이터로 접근할 수 없다.
        ii. 각각의 데이터 엘리먼트들을 "노드"라고 부른다. 노드들은 다음 노드를 가리키는 정보를 저장하고 있고, 더 이상 다음 노드가 없으면 null을 저장한다. 노드가 가진 정보는 다음 노드에 국한된다. 이전 노드에 대한 정보는 없다.
        iii. 노드의 구성
            1) 헤드 : 시작 노드
            2) 테일 : 마지막 노드

b. 장점

        i. 삽입과 제거가 쉽다.

c. Big O

    - 삽입 : O(1). 
    - 제거 : O(1) or O(N)
        § 맨 앞 노드를 제거하면 O(1)이지만 맨 마지막 노드를 제거하는 것은 O(N)이다.
    - 탐색 : O(N)
    - 접근 : O(N)

d. 싱글 연결 리스트를 사용하는 경우

        i. 자료구조의 시작지점에서 제거와 삽입이 빈번히 일어나는 경우.
        ii. 임의적인 접근이 필요 없을 때, 주어진 순서대로 데이터를 관리할 때

e. 예시 코드

    class Node {
      constructor(val) {
        this.val = val;
        this.next = null;
      }
    }
    let first = new Node("Hi");
    first.next = new Node("nice");

next는 다음 노드에 대한 정보를 담고 있다.

하지만 이 경우 계속해서 Node를 생성하고, .next.next.next 이런식으로 next를 추가하여 정보를 입력해야 한다. 이를 위해 새로운 메서드인 push를 만들어준다.