[자료구조] 선형구조

Benzy·2023년 10월 8일
자료구조
0

자료구조, 알고리즘

목록 보기
1/5
post-thumbnail

개요

자료구조는 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타낸다.

개발자는 프로그램을 작성할 때 먼저 자료구조를 선택해 데이터를 어떻게 저장하고 사용할지 결정하고, 이에 맞는 알고리즘을 통해 데이터를 가공하고 원하는 결과를 얻는 과정을 거치게 된다. 그렇기 때문에 상황에 맞는 적절한 자료구조를 택하고 이에 맞는 적절한 알고리즘을 적용할 수 있는 능력이 필요하다.

어떠한 문제를 해결하기 위해서 사용할 수 있는 알고리즘은 여러 종류가 있다. 그렇기 때문에 더 좋은 알고리즘을 선택해야 하는데, 그렇다면 좋은 알고리즘은 무엇일까?

시간 복잡도

좋은 알고리즘은 사용자의 요구에 따라 다를 수 있다. 메모리를 적게 사용하는 방향, 속도가 빠른 방향 등 사용자에 따라 중요시하는게 다르지만 일반적으로는 알고리즘의 속도를 성능의 척도로 사용한다.

성능의 척도를 나타내기 위해서는 시간 복잡도를 사용할 수 있다. 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 말한다. 하지만 시간을 측정해서 알고리즘을 평가하기엔 사용자마다 컴퓨터 사양이 다르기 때문에, 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측한다.

그렇다면 코드에서 많은 영향을 주는 부분은 어떤 것일까?

반복문이다. 반복문이 여러번 반복될수록 실행시간이 길어진다. 따라서 특정 알고리즘의 성능을 평가할 때는 해당 알고리즘의 반복문을 분석하여 시간 복잡도를 추정하는 것이 일반적이다.

빅 오 표기법

알고리즘의 복잡도를 표현하기 위해서는 여러 표기법을 사용할 수 있다.
빅 오(Big O) 표기법은 알고리즘의 최악의 경우를 표현한다.
빅 오메가 (Big Ω) 표기법은 최선의 경우를 표기한다.
빅 세타 (Big Θ) 표기법은 평균의 경우를 표기한다.

주로 빅 오 표기법을 사용하며, 빅 오 표기법의 특징에는 아래와 같은 것들이 있다.

  • 최악의 성능일 때를 가정해서 나타낸다.
  • 계산에 가장 많이 영향을 미치는 항만 표기한다. 예를 들어, 알고리즘의 시간 복잡도가 3n^2 + 4n + 5라면, 이를 O(n^2)으로 표현합니다.
  • 빅 오 표기법은 입력이 늘어날 때 계산량이 늘어나는 척도를 나타내기 위한 것이다.

선형 구조

배열

배열을 선언할 때에는 배열의 크기를 같이 알려주어야 한다.

int arr[10] = {1, 2, 3, 4, 5};

운영체제는 메모리에서 숫자 10개가 들어갈 수 있는 연속된 빈 공간을 찾아 순서대로 1, 2, 3, 4, 5를 할당한다.

운영체제는 배열의 시작 주소를 기억한다. 배열의 접근은 배열의 길이에 상관없이 한 번에 가져오기 때문에 O(1)의 성능을 가진다.

배열은 읽기와 쓰기 즉, 참조에서 좋은 성능을 보인다.

하지만 데이터의 삽입, 삭제의 성능은 좋지 않다.

배열을 선언할 때 운영체제는 미리 확보한 메모리 공간에 쓰레기 값을 덮어 씌우면서 할당된 공간을 차지한다.

이때, 프로그래머가 배열의 크기를 넘어서 할당하게 된다면 운영체제는 크기가 15인 연속된 메모리 공간을 다시 찾아서 할당하고, 기존의 1부터 10까지의 데이터를 복사해서 재할당 해주어야 한다.

자바스크립트에서의 배열은 상황에 따라 연속적, 불연속적으로 할당하며 불연속적인 경우 내부적으로 연결되어 있다.

배열의 장점

  • 읽기, 쓰기와 같은 참조에 O(1)의 성능을 가진다.

배열의 단점

  • 크기 예측이 힘들기 때문에 메모리 낭비가 발생할 수 있다.
  • 데이터 삽입, 삭제가 비효율적이다.

연결리스트 (Linked List)

연결리스트의 개념

노드 (Node)

  • 연결리스트의 구성요소
  • 데이터를 담는 변수 1, 다음 노드를 가리키는 변수 2로 구성되어 있다.
  • 연결 리스트는 첫 노드의 주소를 알고 있다.

연결리스트의 장점

  • 초기 크기를 알아야하는 배열의 단점을 보완할 수 있다.
  • 배열은 데이터 삽입 시의 오버헤드가 많이 든다. (삽입 데이터 기준 뒤의 데이터들은 모두 뒤로 밀려나기 때문) 반면, 연결리스트는 중간에 데이터가 삽입되더라도 다음을 가리키는 노드를 바꿔주면 되기 때문에 비교적 간단하다.

연결리스트의 단점

  • 배열은 시작 주소만 알면 뒤에 있는 데이터 접근이 쉽다. O(1)의 성능을 가진다. 반면, 연결리스트는 데이터들이 전부 떨어져있기 때문에 바로 접근할 수 없다. O(n)의 성능을 가진다.

배열연결리스트
크기고정동적
주소연속불연속
데이터 참조O(1)O(n)
삽입과 삭제O(n)O(n)

연결리스트의 구현

추상 자료형이란?

어떠한 데이터와 그 데이터에 대한 연산

연결 리스트의 추상 자료형

  1. 모든 데이터 출력 - printAll()
  2. 모든 데이터 제거 - clear()
  3. 인덱스 삽입 - insertAt(index, data)
  4. 마지막 삽입 - insertLast(data)
  5. 인덱스 삭제 - deleteAt(index)
  6. 마지막 인덱스 제거 - deleteLast()
  7. 인덱스 읽기 - getNodeAt(index)
// LinkedList.mjs

class Node {
  // data는 필수값이지만 next는 입력하지 않는다면 null 할당
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.count = 0;
  }

  printAll() {
    let currentNode = this.head;
    let text = '[';

    while (currentNode !== null) {
      text += currentNode.data;
      currentNode = currentNode.next;

      if (currentNode !== null) {
        text += ',';
      }
    }

    text += ']';
    console.log(text);
  }

  clear() {
    this.head = null;
    this.count = 0;
  }

  insertAt(index, data) {
    if (index > this.count || index < 0) {
      throw new Error('범위를 넘어갔습니다.');
    }

    let newNode = new Node(data);

    if (index == 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let currentNode = this.head;

      for (let i = 0; i < index - 1; i++) {
        currentNode = currentNode.next;
      }
      newNode.next = currentNode.next;
      currentNode.next = newNode;
    }
    this.count++;
  }

  insertLast(data) {
    this.insertAt(this.count, data);
  }

  deleteAt(index) {
    if (index >= this.count || index < 0) {
      throw new Error('제거할 수 없습니다.');
    }

    let currentNode = this.head;

    if (index == 0) {
      let deleteNode = this.head;
      this.head = this.head.next;
      this.count--;
      return deleteNode;
    } else {
      for (let i = 0; i < index - 1; i++) {
        currentNode = currentNode.next;
      }

      let deleteNode = currentNode.next;
      currentNode.next = currentNode.next.next;
      this.count--;
      return deleteNode;
    }
  }

  deleteLast() {
    return this.deleteAt(this.count - 1);
  }

  getNodeAt(index) {
    if (index >= this.count || index < 0) {
      throw new Error('범위를 넘어갔습니다.');
    }

    let currentNode = this.head;
    for (let i = 0; i < index; i++) {
      currentNode = currentNode.next;
    }

    return currentNode;
  }
}

export { Node, LinkedList };

스택 (Stack)

스택은 Last In, First Out (LIFO) 규칙을 가지고 있는 리스트이다. 즉, 먼저 들어간 데이터가 나중에 나오는 규칙이다.

실행 취소 기능, 문자열을 역순으로 정렬하는 기능, 괄호 검사 등의 사용 사례를 가지고 있다.

스택의 추상 자료형

  • 데이터 삽입 - push()
  • 데이터 제거 - pop()
  • 데이터 참조 - peek()
  • 리스트가 비었는지 체크 - isEmpty()
import { LinkedList } from './LinkedList.mjs';

class Stack {
  constructor() {
    this.list = new LinkedList();
  }

  push(data) {
    this.list.insertAt(0, data);
  }

  pop() {
    try {
      return this.list.deleteAt(0);
    } catch (e) {
      return null;
    }
  }

  peek() {
    return this.list.getNodeAt(0);
  }

  isEmpty() {
    return this.list.count == 0;
  }
}

export { Stack };

큐(Queue)

큐는 리스트로 First In, Last Out 동작을 가능하게 하는 자료구조이다.
운영체제에서도 큐가 쓰이는데, 운영체제는 프로세스의 작업 요청을 요청이 들어온 순서대로 큐에 넣고 CPU가 이를 순서대로 꺼내 처리한다.
이를 운영체제에서는 FIFO 스케줄링이라고 한다.

// 기존 단방향 연결 상태였던 LinkedList를 이중연결리스트로 변경하여 이전 노드를 참조할 수 있도록 수정
class Node {
  constructor(data, next = null, prev = null) {
    this.data = data;
    this.next = next;
    this.prev = prev;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }

  printAll() {
    let currentNode = this.head;
    let text = '[';

    while (currentNode != null) {
      text += currentNode.data;
      currentNode = currentNode.next;

      if (currentNode != null) {
        text += ', ';
      }
    }

    text += ']';
    console.log(text);
  }

  clear() {
    this.head = null;
    this.count = 0;
  }

  insertAt(index, data) {
    if (index > this.count || index < 0) {
      throw new Error('범위를 넘어갔습니다.');
    }

    let newNode = new Node(data);

    if (index == 0) {
      newNode.next = this.head;
      if (this.head != null) {
        this.head.prev = newNode;
      }
      this.head = newNode;
    } else if (index == this.count) {
      newNode.next = null;
      newNode.prev = this.tail;
      this.tail.next = newNode;
    } else {
      let currentNode = this.head;

      for (let i = 0; i < index - 1; i++) {
        currentNode = currentNode.next;
      }
      newNode.next = currentNode.next;
      newNode.prev = currentNode;
      currentNode.next = newNode;
      newNode.next.prev = newNode;
    }

    if (newNode.next == null) {
      this.tail = newNode;
    }
    this.count++;
  }

  insertLast(data) {
    this.insertAt(this.count, data);
  }

  deleteAt(index) {
    if (index >= this.count || index < 0) {
      throw new Error('제거할 수 없습니다.');
    }

    let currentNode = this.head;

    if (index == 0) {
      let deletedNode = this.head;
      if (this.head.next == null) {
        this.head = null;
        this.tail = null;
      } else {
        this.head = this.head.next;
        this.head.prev = null;
      }
      this.count--;
      return deletedNode;
    } else if (index == this.count - 1) {
      let deletedNode = this.tail;
      this.tail.prev.next = null;
      this.tail = this.tail.prev;
      this.count--;
      return deletedNode;
    } else {
      for (let i = 0; i < index - 1; i++) {
        currentNode = currentNode.next;
      }

      let deletedNode = currentNode.next;
      currentNode.next = currentNode.next.next;
      currentNode.next.prev = currentNode;
      this.count--;
      return deletedNode;
    }
  }

  deleteLast() {
    return this.deleteAt(this.count - 1);
  }

  getNodeAt(index) {
    if (index >= this.count || index < 0) {
      throw new Error('범위를 넘어갔습니다.');
    }

    let currentNode = this.head;
    for (let i = 0; i < index; i++) {
      currentNode = currentNode.next;
    }

    return currentNode;
  }
}

export { Node, DoublyLinkedList };

큐의 추상자료형

  • 데이터 삽입 - enqueue()
  • 데이터 제거 - dequeue()
  • 데이터 참조 - front()
  • 리스트가 비었는지 확인 - isEmpty()
import { DoublyLinkedList } from './DoublyLinkedList.mjs';

class Queue {
  constructor() {
    this.list = new DoublyLinkedList();
  }

  enqueue(data) {
    this.list.insertAt(0, data);
  }

  dequeue() {
    try {
      return this.list.deleteLast();
    } catch (e) {
      return null;
    }
  }

  front() {
    return this.list.tail;
  }

  isEmpty() {
    return this.list.count == 0;
  }
}

export { Queue };

덱(Deque)

"Double-Ended Queue"의 약자로, 양쪽 끝에서 항목의 추가와 제거가 모두 가능한 자료구조이다. 큐와 스택의 특성을 합친 것 처럼 볼 수 있다.

덱의 추상자료형

  • 모든 데이터 출력 - printAll()
  • 앞쪽에 데이터 삽입 - addFirst()
  • 앞쪽에서 데이터 제거 후 반환 - removeFrist()
  • 뒤쪽에 데이터 삽입 - addLast()
  • 뒤쪽에서 데이터 제거 후 반환- removeLast()
  • 덱이 비었는지 체크 - isEmpty()
import { DoublyLinkedList } from './DoublyLinkedList.mjs';

class Deque {
  constructor() {
    this.list = new DoublyLinkedList();
  }

  printAll() {
    this.list.printAll();
  }

  addFirst(data) {
    this.list.insertAt(0, data);
  }

  removeFirst() {
    return this.list.deleteAt(0);
  }

  addLast(data) {
    this.list.insertAt(this.list.count, data);
  }

  removeLast() {
    return this.list.deleteLast();
  }

  isEmpty() {
    return this.list.count == 0;
  }
}

export { Deque };
profile
Benzy
상호작용을 구현하는 개발자
다음 포스트

[자료구조] 셋(Set)과 해시 테이블(Hash Table)

0개의 댓글