자료구조 01 배열과 연결 리스트 | JS

배열 | Array

• 논리적 저장 순서와 물리적 저장 순서가 일치
• Random Access 가능: 인덱스(index)로 해당 원소(element)에 접근 가능(Big-O(1))
• 삭제 또는 삽입(O(n))
  : 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 나머지 원소에 대한 인덱스를 조정하는 비용 발생
• 초기화 시 사이즈를 표시하지 않아 유동적이며, 데이터 삭제 시 비는 인덱스가 없는 것으로 미루어 보아 Javascript의 Array는 Arraylist라고 볼 수 있음

연결 리스트 | Linked List

• 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조
• node: data field + next
• 원소들은 자기 자신 다음에 어떤 원소가 오는지만 기억
• 삭제 또는 삽입이 빠르지만, 접근 시간이 선형적이라는 단점.
• 삭제 또는 삽입(O(1))
• Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러남

prepend: 새 노드를 Head로 붙임
append: Tail 뒤에 덧붙임
delete: 삭제
find: 탐색
deleteTail: Tail 삭제
deleteHead: head 삭제

// 새 노드 생성
export default class LinkedListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

import LinkedListNode from './LinkedListNode';

export default class LinkedList {
  constructor(comparatorFunction) {
    this.head = null;
    this.tail = null;
  }

  // 새 노드를 Head로 붙임
  prepend(value) {
    const newNode = new LinkedListNode(value, this.head);
    this.head = newNode;
    // Tail이 아직 없는 경우, 새 노드를 Tail로 설정
    if (!this.tail) {
      this.tail = newNode;
    }
    return this;
  }

  // Tail 뒤에 덧붙임
  append(value) {
    const newNode = new LinkedListNode(value);

    // Head가 없는 경우, 새 노드를 Head로 설정
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return this;
    }

    // 새 노드를 맨 뒤에 붙임
    this.tail.next = newNode;
    this.tail = newNode;

    return this;
  }

  // 삭제
  delete(value) {
    if (!this.head) {
      return null; // head가 없는 경우 = 아무것도 없는 경우
    }

    let deletedNode = null;

    // 헤드를 삭제해야 하는 경우 헤드와 다른 다음 노드를 새 헤드로 만듭니다.
    while (this.head && (this.head.value === value))) {
      deletedNode = this.head;
      this.head = this.head.next;
    }

    let currentNode = this.head;

    if (currentNode !== null) {
      while (currentNode.next) {
        // 다음 노드를 삭제해야 하는 경우, 다음 노드를 '다다음' 노드로 설정
        if (currentNode.next.value === value)) {
          deletedNode = currentNode.next;
          currentNode.next = currentNode.next.next;
        } else {
          currentNode = currentNode.next;
        }
      }
    }

    // Tail을 삭제해야하는지 확인
    if (this.tail.value === value) {
      this.tail = currentNode;
    }

    return deletedNode;
  }

  find({ value = undefined, callback = undefined }) {
    if (!this.head) {
      return null;
    }

    let currentNode = this.head;

    while (currentNode) {
      // If callback is specified then try to find node by callback.
      if (callback && callback(currentNode.value)) {
        return currentNode;
      }

      // If value is specified then try to compare by value..
      if (value !== undefined && (currentNode.value === value)) {
        return currentNode;
      }

      currentNode = currentNode.next;
    }

    return null;
  }

  // Tail 삭제
  deleteTail() {
    const deletedTail = this.tail;

    if (this.head === this.tail) {
      // linked list에 단 하나의 노드만 있을 경우
      this.head = null;
      this.tail = null;

      return deletedTail;
    }

    // If there are many nodes in linked list...

    // 마지막 노드를 찾고, 마지막 노드의 다음 링크를 삭제
    let currentNode = this.head;
    while (currentNode.next) {
      if (!currentNode.next.next) {
        // 현재 노드의 '다다음'이 없으면 다음이 마지막 노드임
        // 마지막 노드를 삭제해야하니 현재 노드의 다음을 삭제
        currentNode.next = null;
      } else {
        currentNode = currentNode.next;
      }
    }

    this.tail = currentNode;

    return deletedTail;
  }
  
  
  // head 삭제
  deleteHead() {
    if (!this.head) {
      return null;
    }

    const deletedHead = this.head;

    if (this.head.next) {
      this.head = this.head.next;
    } else {
      this.head = null;
      this.tail = null;
    }

    return deletedHead;
  }

  // array로 들어온 인자를 연결 리스트에 append
  fromArray(values) {
    values.forEach((value) => this.append(value));

    return this;
  }
  
  // 모든 노드를 배열로 반환
  toArray() {
    const nodes = [];

    let currentNode = this.head;
    while (currentNode) {
      nodes.push(currentNode);
      currentNode = currentNode.next;
    }

    return nodes;
  }

  // 문자열로 반환
  toString(callback) {
    return this.toArray().map((node) => node.toString(callback)).toString();
  }  
}

📚 참고

Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb

Photo by Alain Pham on Unsplash