[자료구조] 배열 vs 링크드리스트

Keyword : 정적 할당, 동적 할당, 연속 저장, 비연속 저장

Q. 배열과 링크드리스트에 대한 차이점을 설명하세요

배열의 의미는 무언가가 나열되어 있다는 표현이다. 말 그대로, 데이터들을 나란하게 저장하겠다는 의미이다. 반면, 링크드 리스트는 저장된 데이터와 다음 데이터를 연결하면서 값들을 저장한다. 따라서 링크드 리스트의 각 원소는 value를 저장할 변수와 다음 데이터의 주소를 저장할 포인터가 필요하다.

Q. 배열과 링크드리스트의 장단점을 생각하며 활용하면 더 좋은 예제를 말해보세요

배열은 일단 간단하고 쉽다 . 속도도 링크드 리스트에 비해 빠르다. 여기서 속도라는 것은 시간 복잡도가 아니라 물리적으로 다음 데이터를 찾는 속도가 빠르다는 것이다. 왜냐하면 배열은 다음 데이터가 연속되어 위치하기 때문이다. 단점으로는 배열은 미리 자원을 할당받아 사용한다. 따라서, 예상치 못한 데이터의 추가, 삭제, 삽입에 유연하지 못하다. 예를 들어 100개의 int value를 저장할 수 있는 배열이 있을 경우, 실제로 저장되는 데이터는 20개일 수도 있다. 그럴 경우 80개의 자원이 낭비가 되는 것이다. 또한, 110 개 데이터가 들어왔을 경우 100을 초과했으므로 나머지 10 개의 데이터는 배열에 저장할 수가 없다. 따라서, 배열은 필요한 값이 거의 완전하게 예측되는 경우에 사용하는 것이 좋다. 또한, 값의 입출력은 용이하나 중간에 값을 삽입한다든지 삭제할 경우 그 뒤에 있는 값들을 옮겨줘야 하기 때문에 오히려 프로그래밍 복잡도가 높아질 수 있다. 

반면 링크드리스트는 구현이 다소 난이도가 있지만 데이터의 삭제, 삽입, 확장, 축소 등에 유연하다. 왜냐하면 필요한 만큼 더 할당받아서 연결해서 사용하면 되기 때문이다. 하지만 데이터를 탐색할 때, 포인터를 타고 타고 가서 필요한 데이터를 찾아야 하기 때문에 물리적인 속도는 다소 느릴 수 있다. 링크드 리스트는 이러한 장점을 가지고 있으므로 확장이 요구되는 상황에서 사용하면 좋다. 예를 들어 도서관리 프로그램에서는 도서가 몇 권 일지 예상이 어렵기 때문에, 확장이 가능하게 설계해야 한다. 이러한 경우 링크드 리스트를 사용하면 좋다.

 

Q. 이진 트리 자료 구조를 배열로 구현하는 방법에 대해서 말해보세요

완전 이진트리가 아닌 그냥 이진트리일 경우 배열로 구현하는 것이 적합하지 않다.

왼쪽 노드는 존재하지 않고 오른쪽만 depth 가 n까지 계속해서 있을 경우... 공간이 1 + 2 + 2^2... + 2 ^(n-1)까지 필요한데 사용하는 노드의 개수는 n개... 뿐이다. 공간 낭비가 너무 심하다. 

 

완전 이진트리 예시

#include <iostream>
 #include <vector>
 using namespace std;

 class Tree {
     public:
         vector <char> nodes_;
     public:
         Tree(int node_size, char root_data) {
             nodes_.resize(node_size);
             nodes_[0]  = root_data;
         }
         void SetLeft(char data, int parents_idx) {
             nodes_[2*parents_idx+1] = data;
         }

         void SetRight(char data, int parents_idx) {
             nodes_[2*parents_idx+2] = data;
         }
         void PrintTree() {
             for(auto &node: nodes_)
                 printf("%c ",node);
             printf("\n");
         }
 };
 int main() {

   /*       A(0)
   *       <-  ->
   *    B(1)      C(2)
   *  <- ->      <- ->
   * D(3)  E(4) F(5)  G(6)
   * */

     Tree t(7, 'A'); // vector <char> nodes (7) nodes[0] = 'A'
     t.SetLeft('B', 0); // nodes[1] = 'B'
     t.SetRight('C', 0); // nodes[2] = 'C'

     t.SetLeft('D', 1);
     t.SetRight('E', 1);

     t.SetLeft('F', 2);
     t.SetRight('G', 2);

     t.PrintTree();  // A B C D E F G
 }