본문 바로가기
기타/자료구조, 알고리즘

[자료구조, 알고리즘] 리스트#2 - LinkedList 구현, syntax + develop tip

by jinbro 2017. 9. 1.
[연결리스트 특징 및 구현할 때 생각해야할 것]
- ArrayList는 배열(array)로 구현된 List, 연결리스트는 메모리에 동적으로 할당되는 데이터들을 하나의 리스트로 만듬
- Node 인스턴스(object)를 동적으로 할당하되 하나의 리스트로 엮음 : LinkedList
- 구현하면서 가장 중요하게 생각해야하는 것 : node간 연결방법, node를 순차적으로 탐색하는 방법


[자바스크립트로 LinkedList 구현하기(feat. 자바스크립트 프로토타입 기반 객체지향)]
- node를 head로만 추가함
=> head 와 tail 추가하는 방법을 구현하면됨
=> 중간 node를 제어하는 방법도 생각해봅시다 : setRuleList 추가

- LinkedList 객체 : 추상화, private / public 멤버 구분하기
/* 단순연결리스트 : 더미노드 버젼 */
var LinkedList = (function() {
function Node(data){
        this.data = data;
        this.next = null;
}

    function LinkedList(){      
/* LinkedList 변수객체, 스코프에 Node 함수 추가 : closure */
        this.head = new Node('리스트에 저장할 데이터를 추가해주세요');
/* only use search or remove */
this.before = null; //단방향이기때문에 오른쪽으로만 참조가능
        this.current = null;
        
this.length = 0;
/* 오름차순 정렬 -> 삽입 */
this.compFunc = null;
}

    
    LinkedList.prototype = {
setSortRule: function(){
this.compFunc = function(compData, standard){
if(compData > standard){
return 1;
} else {
return 0;
}
}

return true;
},

        add: function(data){
if(!data){
console.log('리스트에 추가할 데이터를 입력해주세요');
return false;
}

/* 더미노드를 만듬으로서 this.head null check를 하지않아도됨 */
var dummyNode = this.head;
var newNode = new Node(data);

var compFunc = this.compFunc;
if(compFunc && this.length > 0){
var compNode = this.head;

while(compNode.next && compFunc(data, compNode.data) != 0){
console.log(compNode.data + ", " + compNode.next.data);
compNode = compNode.next;
}

var temp = compNode.next;
compNode.next = newNode;
newNode.next = temp;

} else {
if(dummyNode.next){
var temp = dummyNode.next;
dummyNode.next = newNode;
newNode.next = temp;
} else {
dummyNode.next = newNode;
}

}
this.length += 1;

return newNode;
},

        first: function(){
var dummyNode = this.head;
if(dummyNode.next){
// 더미노드 다음 노드가 삭제됐을 때 더미노드에 null처리를 하기위해서는 여기서도 before을 등록해줘야
this.before = dummyNode;
this.current = dummyNode.next;
return true;
} else {
return false;
}
},

next: function(){
var curr = this.current;

if(curr && curr.next){
this.before = curr; /* to connect after remove */
this.current = this.before.next; // call by reference, value
return true;
} else {
return false;
}
},

        remove: function(){
var before = this.before;
var current = this.current;
var length = this.length;
var removeData = current.data;
if(current && length > 0){
if(length === 1){
before.next = null;
} else {
before.next = current.next;
}
this.current = before;
this.length -= 1;
return removeData;
} else {
return false;
}
},

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

    return LinkedList;

})();


var list = new LinkedList();


[보너스 트랙 : 자바스크립트 객체, 즉시실행함수 IIFE, syntax & develop tip]
[객체]
- 자바스크립트는 클래스가 없음 : 자바를 첫 프로그래밍 언어로 접했던 나로서는 처음엔 굉장히 힘들었음
- 자바스크립트는 함수가 생성자가 되고(초기화), 추상 객체(멤버 선언, 공통된 멤버는 함수의 prototype 객체) 역할을 함
- new 키워드를 통해 인스턴스를 생성함


[IIFE란]
- 즉시실행함수의 약자
- 함수표현식의 일종 : function 함수명() - 함수선언식 이 아니면 함수표현식
- 즉시실행함수를 왜 쓰나요?
(1) 즉시실행함수 이름 그대로 선언과 동시에 실행 : 함수자체는 전역컨텍스트의 변수객체에 선언되지않음
(2) 즉시실행함수를 변수에 저장할 경우 즉시실행함수의 결과값만 저장
=> private 변수 선언(set을 만들어주지않으면 변경 불가)
=> 클로저 활용할 수 있음 - 대다수의 라이브러리들이 사용하는 방법(네임스페이스 생성)
var init = (function(){
var name = ‘jinbro’;

function get(){
return name;
}

return get;
})();

init; // function get의 구현부가 출력됨
init(); // get 함수 호출 - name 클로저 -> jinbro 출력


[syntax + develop tip]
- 거짓으로 취급되는 값
(1) false
(2) undefined
(3) null
(4) 0
(5) NaN
(6) ""

- call by value 와 call by reference
(1) var a = 1; var b = a; : a와 b는 같지않음, 각각의 메모리 공간에 값을 복사하는 것(call by value)
(2) var a = { }; var b = a; : a와 b는 같은 객체(메모리 주소)를 가리킴, b에 a가 가리키는 객체의 메모리주소를 복사(call by reference)
=> this.current를 변수에 담는다 : this.current가 가리키는 node의 주소값을 똑같이 참조
=> 변수에 담기는 객체 주소값을 변경한다고해서 this.current가 변경되는 것 아님 : this.current = this.current.next로 직접 변경해야함
=> current = this.current.next : 변수 current가 가리키는 주소값만 변경(참조 객체만 변경하는 것)
=> current.data 이렇게 참조 객체의 멤버를 변경하는 것은 되지만 current가 가리키는 객체의 주소값 자체를 변경하는 것은 앞과 다른 상황임
=> 일반값과 객체를 담는 변수가 어떤 것을 담는지는 알아야함

- 오름차순, 내림차순 기준 함수 : 함수의 결과값 + 어떻게 배치하느냐
function compFunc(data, standard){
if(data > standard){
return 1;
} else {
return 0;
}
}

while(compFunc(data, standard) != 0){
기준값을 다음 리스트 요소로 넘기는 코드
}

리스트에 데이터 추가 코드
=> 추가하려는 data가 기준이 되는 statndard보다 클 경우 1을 리턴
=> 1일 떄에는 모두 넘김 : data가 standard보다 클 경우는 스킵
=> 추가하려는 데이터가 비교 기준 standard보다 작을 경우 추가 - 오름차순
=> compFunc의 비교 수식을 반대로 바꾼다면 내림차순으로 변경됨 혹은 return 되는 값 변경

- 한꺼번에 개발하지말자 : 테스트하면서, 한꺼번에 개발해놓고 테스트했는데 안되기 시작하면 고치기도 더 힘들어진다



댓글