[자료구조 알고리즘] 리스트#1 - ADT, ArrayList js구현, syntax tip

[리스트 특징]

- 1열에 나란히 데이터를 저장함 : 1줄로 연결된 형태, 탐색

- 중복된 데이터를 허용함
- 데이터 참조가 쉬움, 내부적으로 index를 기반으로 first / next 동작
- 삭제 과정에서 이동이 빈번하게 일어남, 외부적으로는 index를 기준으로해서 옮기는 것이 아니라 first / next 함수를 호출해서 cursor를 움직임

=> 탐색이 빈번하게 일어나는 기능에서 자료를 저장하는 구조로서는 부적합

[리스트 구현방법에 따른 종류]

- 주의할 점 : 구현 방법에 따라 나눈 것이지 ADT가 다른 것이 아님

- 순차리스트 : 배열을 가지고 구현한 리스트

- 연결리스트 : 메모리 동적할당을 가지고 구현한 리스트

[C로 배운 리스트 자바스크립트로 구현하기]

- 어차피 ADT가 달라지는 것도 아니고, 언어적 특성만 고려해서 그에맞게 짜면됨 : 매커니즘은 같음

- 그나마 자세하게 언어적 특성을 이해하고있는건 자바스크립트라 자바스크립트로 구현하기

- 자바스크립트도 c처럼 자료구조 관련해서는 array만 있음 : 물론 라이브러리는 있겠지만

[리스트 ADT]

- 리스트 초기화

- 리스트 요소 저장

- 리스트 첫번째 요소 리턴

- 리스트 다음 요소 리턴

- 리스트 요소 삭제

- 리스트 길이 조회

[리스트 구현 - 자바스크립트로다가]

var ArrayList = (function() {
  
    var ArrayList = function() {
        this.arr = [];
        this.curPos = -1;
        this.data;
    }

    ArrayList.prototype = {
        add: function(arg) {
            var params = ArrayList.prototype.add.arguments;

            if (params.length < 1) {
                console.log('추가할 데이터를 입력해주세요');
                return false;
            } else {
                for (let i = 0; i < params.length; i++) {
                    this.arr.push(params[i]);
                }
                return true;
            }
        },

        first: function() {
            if (this.arr.length < 1) {
                return false;
            } else {
                this.curPos = 0;
                this.data[0];
                return true;
            }
        },

        next: function() {
            if (this.curPos < 0 || !this.arr[this.curPos + 1]) {
                return false;
            } else {
                this.curPos += 1;
                this.data[this.curPos]
                return true;
            }
        },

        get: function() {
            if (this.curPos < 0) {
                return false;
            } else {
                return this.data;
            }
        },

        remove: function() {
            if (!this.arr[this.curPos]) {
                return false;
            } else {
                var temp = this.arr[this.curPos];
                this.arr.splice(this.curPos, 1);

                this.curPos -= 1; // -1로 진입하면 아무것도 못함
                return temp;
            }
        },

        count: function() {
            return this.arr.length;
        }
    }

    return ArrayList;
})();

=> prototype : ArrayList 로 인스턴스를 생성하는 모두에게 공통적으로 주어짐 - 메모리 효율(this로 생성하면 각 객체에 생성되기떄문에)

                         __proto__ : prototype 참조 + constructor 변수 객체

=> remove 할 때 curPos : 참조가 이뤄진 최근 데이터를 가리키는 index임, 삭제 후 하나씩 당겨오는 과정에서 curPos가 삭제된 요소 뒤의 요소를 가리키게되는데
                                         논리적으로는 삭제 전의 최근 데이터를 가리켜야하므로 -1을 해줌

=> remove 할 때에는 삭제할 데이터 반환해주기 : 리스트 자료구조는 데이터(값)의 주소값을 저장하는 자료구조, 삭제한다는 것은 리스트에서 특정 주소값을 삭제하는 것
                                                                           삭제하는 데이터를 반환해줌으로서 free()를 호출하여 메모리를 해제할 수 있도록 하기위해 데이터를 반환(C 언어)

=> 자바스크립트 배열은 동적할당 : c였다면 malloc을 사용해서 동적할당한 뒤 사용 완료되면 free를 호출함, 자바스크립트는 가비지컬렉션이 할당된 메모리 관리해줌
    자동이지만 가비지컬렉터가 비활성화된 메모리인지 정확하게 구분하기 어렵기때문에 명시적으로 null을 대입함

[보너스 트랙 - 자바스크립트 syntax tip]

(0) 스코프 형성(컨텍스트 생성 - 4번 항목볼 것) : 전역, 함수, eval

(1) 전역변수를 가급적이면 선언하지않는 것이 좋음 : window 스코프

=> 변수가 섞일 수 있기때문에 : 덮어쓰기됨(window.변수)

=> 함수 내 지역변수로 선언해서 사용할 것

=> 고유의 네임스페이스를 만들어 사용할 것 : object type variable사용

var JINBRO = {
	age: 26,
	
	getAge: function(){
		alert(this.age);
	}
}

JINBRO.age // 26

=> 네임스페이스라는 것이 어떻게 구현되는지 보여주기위한 예시일뿐입니다

=> 제이쿼리 : $ / 페이스북 : FB / 네이버 : jindo

=> 외부에서 변경가능함 : 변수 하나만 변경하더라도 모든 함수에 영향을 미침

var JINBRO = (function() {
    var age = 26;

    return {
        getAge: function() {
            return age;
        }
    };
})();

=> JINBRO에 리턴값을 저장 : JINBRO 네임스페이스, 즉시실행함수표현식(IIFE)

=> private : age  /  public : getAge()

=> 모듈패턴 : 라이브러리를 만들 때 기본 - 비공개 변수를 만들어줌

=> 하나의 객체를 생성

=> getAge가 IIFE 변수 age 클로저 : age를 참조

=> IIFE : 함수를 변수에 저장하지않고 호출 결과값을 변수에 저장

(2) 외부함수 -> 내부함수 접근 불가 : 스코프 서치 방향은 내부 -> 외부 -> 전역(스코프체인)

(3) 렉시컬 스코핑 : 함수 선언 시기에 스코프 생성 - 선언될 때 존재하지않는 값은 undefined처리(변수 자체가 안생김, 초기화는 따로)

var age = 99;

var outer = function() {
    function inner(arg) {
        var age = arg ? arg : 0;
    }


    inner.prototype = {
        getAge: function() {
            return age;
        }
    }

    return inner;
}();

var jinbro = new outer(26);

=> 잘못된 자바스크립트 프로그래밍 : 스코프가 생성되는 과정(컨텍스트 생성)을 알면 제대로 코딩할 수 있지

(4) 실행컨텍스트 : 전역 / 함수 실행컨텍스트

- 실행컨텍스트 : 변수객체, 스코프체인, this 생성

- 처음 코드가 실행되면(스크립트가 돌아가면) 전역 실행컨텍스트 생성 : 페이지 종료까지 유지

=> 변수객체 : window 스코프 변수들

=> this : 따로 설정하지않으면 window (new, bind, apply 등으로 변경가능)

=> 스코프체인 : 자신을 포함한 상위 스코프, 전역은 없으니 window만

=> argument(함수 인자) 존재하지않음

'전역 컨텍스트': {
    변수객체: {
        arguments: null,
        variable: [

        ]
    },
    this: window,
    [[Scopes]]: ['위에 있는 전역 변수객체']
}

=> 전역 컨텍스트 변수객체 변수에 값 대입

- 함수 호출 시 함수 컨텍스트 생성 -> 함수 실행 -> 사용되는 변수는 변수객체에서 찾음, 없다면 스코프 체인을 따라 서치, 함수 종료 시 컨텍스트 제거

=> 함수() 로 호출하는 순간 함수컨텍스트 생성

'함수 컨텍스트': {
    변수객체: {
        arguments: null,
        variable: ['변수명']
    },
    this: window,
    [[Scopes]]: ['함수 변수객체'],['전역 변수객체']
}

=> arguments : 함수 인자로 받는 것이 있으면 null 아님

=> this : 따로 설정해주지않았기때문에 window(default)

=> 변수 객체 내 variable ['변수명'] : 변수에 넣는 값이 대입되면(초기화) 바뀜 - undefined에서 바뀜

=> 선언되지않고 호출하는 변수는 변수객체에 포함되지않음 : 스코프 서치함(스코프체인)

var name = 'jinbro';

function a() {
    console.log(name);
}

function b() {
    var name = 'jinhyung';
    console.log(name);

    a();
}

=> a를 스코프체인 : 상위 변수객체(window)에서 발견 -> 실행 -> a 실행컨텍스트 생성 -> a 호출
     -> [[Scopes]]는 선언 시에 이미 정해져있음(b 스코프가 a [[Scopes]]에 들어가지않음) - 렉시컬 스코핑

(5) 호이스팅 : 변수 선언문을 모두 최상단으로 끌어올림(전역 컨텍스트와 관련 - 코드 실행이 된 뒤 초기화문을 만나면 변수객체 변수에 대입)

=> 함수 선언식( function 함수명() {} )은 함수 실행문까지 모두 끌어올림됨 : 선언 코드보다 호출문이 앞에 있어도 아무런 문제없이 실행됨(끌올)

=> 함수 표현식 ( var 함수명 = function() {} )은 변수만(함수명) 끌어올림됨 : 변수객체 variable에 포함, [[Scopes]] window의 스코프에도 추가

(6) 클로저 

var closureTest = function() {
    var name = ‘jinbro’;

    return {
        getName: function() {
            return name;
        }
    }
}

var closure = closureTest();

=> 컨텍스트 관점에서 보기

'전역 컨텍스트’: {
	변수객체: {
        arguments: null,
        variable: [{
            closureTest: function
        }, closure]
    },
    this: window, [[Scopes]]: [‘전역 변수객체’]
}

'closureTest 변수객체': {
    변수객체: {
        arguments: null,
        variable: [name]
    },
    this: window,
    [[Scopes]]: [‘closure 변수객체’],[‘전역 변수객체’]
}

'closure 변수객체': {
    변수객체: {
        arguments: null,
        variable: null
    },
    this: window,
    [[Scopes]]: [‘closure 변수객체’], [‘closureTest 변수객체’],[‘전역 변수객체’]
}

=> 스코프 체인을 통해서 closureTest 변수객체의 name을 참조해서 리턴

=> 비공개변수를 만들고 클로저를 활용해서 공개된 함수를 통해서만 조작되도록 함

=> 메모리릭 이슈가 발생할 수도 있음 : 스코프 체인을 통해서 거슬러 올라가는 것이 느려지는 것에 원인

(7) 디자인 패턴

- 모듈 패턴 : private / public 구분

var JINBRO = (function() {
    var name = ‘jinbro’;

    return {
        getName: function() {
            return name;
        }
    }
})();

=> getName return name : IIFE name closure

- 싱글턴 : 생성자로 단 하나의 인스턴스를 만들 때 사용

var singleton = (function() {
    var instance;
    /* private variable */
    var name = ‘jinbro’;
    var age = 26;

    function init() {
        return {
            getAge: function() {
                return age;
            },
            getName: function() {
                return name;
            }
        }
    }
    return {
        getInstance: function() {
            if (!instance) {
                instance = init();
            }
            return instance;
        }
    }
});

var first = singleton.getInstance();
var second = singleton.getInstance();
console.log(first === second); // true

=> singleton 변수 : 함수 호출 -> return 객체(+ getInstance 메서드) -> 객체.getInstance 호출 -> (instance가 undefined일 떄) instance = init() -> init() 호출 -> private 변수 리턴

=> 네임스페이스를 만들 때 사용, 프로젝트의 가장 최상위 객체(단 하나)

- 생성자 : 여러개의 인스턴스 생성, 상속(부모 생성자의 기능을 물려받으면서 새로운 기능을 추가 - Vehicle - Sedan, SportsCar)

var ArrayList = (function(){
	function ArrayList(){
		this.arr = [];
		this.curPos;
		this.data;
	}

	ArrayList.prototype = {
		/* 메서드 */
	}

	return List;
})();

=> 모듈 패턴 혼용 : IIFE(즉시실행함수표현식)

=> ArrayList 덮어쓰기