List형 자료구조

리스트형 자료구조는 연속적인 저장의 형태를 가지며, 두 가지가 있다.

• 배열 : 크기가 변하지 않는 리스트형 자료구조, 중간의 값을 지워도 빈칸을 유지한다.
• 리스트 : 크기각 변하는 자료구조, 중간의 값을 지우면 뒤의 것이 그 자리를 채우려고 앞으로 이동한다.

List 구현

그럼 자바스크립트로 List를 구현해보자!

class List {
  constructor() {
    this.listSize = 0;
    this.position = 0;
    this.data = [];
  }
	
  // length 프로퍼티처럼 접근 가능 (ES6)
  get length() {
    return this.listSize;
  }
	
  // 요소 추가
  append(element) {
    this.data[this.listSize] = element;
    this.listSize++;
  }
	
  // 요소 index 반환
  find(element) {
    for (let i = 0; i < this.listSize; i++) {
      if (this.data[i] === element) return i;
    }
    return -1;
  }
	
  // 요소 제거
  remove(element) {
    let foundAt = this.find(element);
    if (foundAt > -1) {
      this.data.splice(foundAt, 1);
      this.listSize--;
      return true;
    }
    return false;
  }

  // 리스트 출력
  printElement() {
    return this.data;
  }

  // 특정 요소 다음에 요소 삽입
  insert(element, after) {
    let insertPosition = this.find(after);
    if (insertPosition > -1) {
      this.data.splice(insertPosition + 1, 0, element);
      this.listSize++;
      return true;
    }
    return false;
  }

  // 리스트 요소 전체 제거
  clear() {
    this.data = [];
    this.listSize = 0; 
  }

  // 맨 앞의 요소로 현 위치 이동
  front() {
    this.position = 0;
  }

  // 맨 뒤의 요소로 현 위치 이동
  end() {
    this.position = this.listSize - 1;
  }

  // 이전 요소로 현 위치 이동
  prev() {
    if (this.position === 0) {
      return true;
    }
    this.position--;
  }

  // 다음 요소로 현 위치 이동
  next() {
    if (this.position === this.listSize - 1) {
      return true;
    }
    this.position++;
  }

  // 현 위치 반환
  currentPosition() {
    return this.position;
  }

  // 특정 위치로 이동
  moveTo(position) {
    this.position = position;
  }

  // 현 위치의 요소 반환
  getElement() {
    return this.data[this.position];
  }
}

const list = new List();

list.append(1);
list.append(2);
list.append(3);
console.log(list.length); // 3
console.log(list.find(2)); // 1

list.remove(2);
console.log(list.length); // 2

list.clear();
console.log(list.length); // 0

list.append(1);
list.append(2);
list.append(3);
list.append(4);
list.append(5);
console.log(list.length); // 5

list.front();
console.log(list.getElement()); // 1

list.end();
console.log(list.getElement()); // 5

list.prev();
list.prev();
console.log(list.getElement()); // 3

list.next();
console.log(list.getElement()); // 4

확실히 직접 구현해보니까 List가 이런 식으로 구현되는구나 하고 직접 와닿는 것 같다. 되게 재밌네.