[자바스크립트 자료구조] List

[List]

- 목록, 순서가 있는 일련의 집합체(몇번째 항목)

- 리스트에 저장된 각 데이터 항목을 요소라 함, 프로그램의 가용메모리가 리스트에 저장할 수 있는 최대 요소 수

- Array의 index 버림(빠른 검색X), 요소간의 순서가 중요, 빈 엘리먼트 허용X : 리스트 탐색을 통해 요소 추출

- 빈틈없는 데이터 적재의 장점을 취한 자료구조 : Array는 index 자리에 value가 삭제되면 뻥 떠버림 - 메우기위한 로직 필요

=> Array 단점 보완 : 크기 고정X(새로 빈 배열을 만들고 깊은 복사를 해서 만드는 방식이 아님)

[List ADT]

- ADT란? Abstract Data Type을 말함, 리스트 자료구조가 어떤 구현부를 가져야하는가를 인터페이스 제시하는 것

- 예시 : 전기밥솥 ADT : 밥(자료), 취사/예약취사/취소 버튼, 시간 표시 디스플레이에 어떤 내용이 표시되어야하는지 명기하는 것

1) listSize(프로퍼티): 리스트 요소 수

2) pos(프로퍼티) : 현재 위치

3) length(프로퍼티) : 리스트 요소수 반환

4) clear(함수): 모든 요소 삭제

5) toString(함수) : 리스트를 문자열로 표현해 반환

6) getElement(함수) : 현재 위치의 요소를 반환

7) insert(함수) : 기존 요소 위로 새 요소를 추가

8) append(함수) : 새 요소를 리스트 요소 끝에 추가

9) remove(함수) : 리스트의 요소 삭제

10) front(함수) : 현재 위치(탐색 위치)를 리스트 첫번째 요소로 설정

11) end(함수) : 현재 위치를 리스트 마지막 요소로 설정

12) prev(함수) : 현재 위치를 한 요소 뒤로 이동

13) next(함수) : 현재 위치를 한 요소 앞으로 이동

14) currPos(함수) : 리스트의 현재 위치 반환

15) moveTo(함수) : 현재 위치를 지정된 위치로 이동

[List 추상화]

- 자바스크립트는 클래스가 없음, 함수가 객체 역할(인스턴스 변수, 메서드 구현)

- List 추상 객체 역할을 할 function 구현하기

- 자바스크립트 표준 내장객체 Array를 이용해서 List를 구현함(Array 래핑) : Array.prototype 객체 메서드 사용

- 배열로 만들지만 추상화된 List 객체를 인스턴스 생성해서 사용 : listName.메서드 혹은 프로퍼티

var List = function(){
    this.dataStore = [];
    this.pos = 0;
    this.listSize = 0;
}

1) append : 리스트 마지막 요소 다음 순서에 추가 : 크기 늘려주기

List.prototype.append = function(element){
     this.dataStore[this.listSize] = element;
     this.listSize++;
}

- 기본적으로 listSize를 구현해야함 : 배열의 length, size

2) find : 특정 값이 리스트에 포함되어있는지 있다면 position을 리턴해줌, 없으면 -1 리턴

List.prototype.find = function(element){
      for(var i=0; i<this.listSize; i++){
          if(this.dataStore[i] === element){
                return i;
          }
      }
      return -1;
}




3) remove : 특정 값을 가진 요소를 찾고, 요소를 삭제하고, 당기고 - 빈틈 없는 데이터 적재

List.prototype.remove = function(element){
    var removePos = this.find(element);

    if(removePos > -1){
      this.dataStore.splice(removePos, 1);
      this.listSize--;
      return true;
    }
    return false;
}

- 기본적으로 remove를 호출했을 때 false이고, 특정 상황에 일치할 때 true가 되도록 코드를 짜야함

- 내부적으로는 array의 splice 메서드를 사용해서 삭제




4) length : 리스트에 저장된 요소의 개수

List.prototype.length = function(){
    return this.listSize;
}

5) toString : 리스트 요소 확인

List.prototype.toString = function(){
    return this.dataStore;
}

6) insert : 기존 리스트 뒤에 추가하기 - index 안씀

List.prototype.insert = function(element, after){
    var insertPos = this.find(after);

    if(insertPos > -1){
      this.dataStore.splice(insertPos+1, 0, element);
      this.listSize++;
      return true;
    }

    return false;
}

- 앞서 구현한 find를 헬퍼로 사용

- after : 기존 요소 값




7) clear : 리스트 모든 요소 제거

List.prototype.clear = function(){
    this.dataStore = [];
    this.listSize = 0;
    this.pos = 0;
}

8) contains : 특정 값이 요소로 존재하는지 판단

List.prototype.contains = function(element){
    for(var i=0; i

- find와 같음

9) 리스트 탐색과 관련된 메서드

/* 탐색 위치를 맨 앞의 요소로 */
List.prototype.front = function(){
    this.pos = 0;
}

/* 탐색 위치를 맨 뒤의 요소로 */
List.prototype.end = function(){
    this.pos = this.listSize-1;
}

/* 현재 탐색 위치보다 이전으로 이동 */
List.prototype.prev = function(){
    if(this.pos > 0){
        this.pos--;
    }
}

/* 현재 탐색 위치보다 이후로 이동 */
List.prototype.next = function(){
    if(this.pos < this.listSize-1){
        this.pos++;
    }
}

/* 현재 탐색 position 리턴 */
List.prototype.currPos = function(){
    return this.pos;
}

/* 탐색 위치 이동 */
List.prototype.moveTo = function(position){
    if(position < this.listSize){
        this.pos = position;
    }
}

/* 현재 탐색 위치에 있는 요소 리턴받기 */
List.prototype.getElement = function(){     
    return this.dataStore[this.pos];
}

- 리스트 요소를 탐색하면서 요소를 리턴받음

- index로 요소를 찾는 것이 아니라 this.pos(탐색 위치)로 탐색위치를 옮겨다니면서 요소를 찾아서 뽑음

=> this.pos가 중요







[리스트 순차적으로 출력하기]

for(리스트명.front(); 리스트명.currPos() < 리스트명.length(); 리스트명.next()){
     console.log(리스트명.getElement());
}

for(리스트명.end(); 리스트명.currPos() >= 리스트명.front(); 리스트명.prev(){
     console.log(리스트명.getElement());
}

[정리]

- 리스트는 인덱스(index - value)가 아니라 데이터가 저장되어있는 위치(position), 탐색

- 자료구조 열심히

- 상황에 맞는 자료구조 사용하기







[참고자료]

- 도서, 자바스크립트 자료구조와 알고리즘