[CS 면접 대비] 자료구조/알고리즘 선형 자료구조(Array, List, HashTable, Queue, Stack) 개념 & 질문 정리

선형 자료구조 (목차)

• Array
• List
• HashTable
• Queue
• Stack

---

 

선형자료구조란? : 원소들을 순서대로 나열한 집합

 

---

 

*선형 자료구조에 대해 정리하기 전, 먼저 전체적인 자료구조의 형태를 이해하기 위해 아래 이미지를 첨부한다.

자료구조의 형태

---

 

1. Array(배열)

: 배열이란 같은 성질을 갖는 항목들의 집합

메모리 상에 연속적으로 데이터가 저장된 연접 리스트(순차 리스트)에 해당한다. (데이터 참조 시 Index 사용)

** Array 특징

• 고정된 크기
  • 배열의 크기를 10으로 지정한다면, 내부에 데이터가 5개만 있더라도 실제 배열의 크기는 10이다.
    ** 메모리가 낭비될 수 있다.
• 논리적 저장 순서와 물리적 저장 순서가 일치하다. (메모리 상에 데이터도 순차적으로 저장된다.)
• Cache Hit Rate 가 높다.
• 추가적으로 소모되는 메모리 양(오버헤드)이 거의 없다.
• 삽입과 삭제의 경우 O(N)의 시간 복잡도를 갖는다.
• 원소에 접근할 때는 O(1)의 시간 복잡도를 갖는다.
• 기억 장소를 미리 확보해야 한다.

면접 질문 !

? ? Array의 가장 큰 특징과 그로 인해 발생하는 장단점

: Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점입니다. 데이터에 순서가 있기 때문에 0부터 시작하는 index가 존재하며, index를 사용해 특정 요소를 찾고 조작이 가능하다는 것이 Array의 장점입니다. 순차적으로 존재하는 데이터의 중간에 요소가 삽입되거나 삭제되는 경우 그 뒤의 모든 요소들을 한 칸씩 뒤로 밀거나 당겨줘야 하는 단점도 있습니다. 이러한 이유로 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절치 않습니다.

 

? ? Array를 적용시키면 좋을 데이터의 예 / 구체적 예시와 함께 Array를 적용하면 좋은 이유, 그리고 Array를 사용하지 않으면 어떻게 되는지

: Array를 적용시키면 좋은 예로 주식 차트가 있습니다. 주식 차트에 대한 데이터는 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며, 날짜별로 주식 가격이 차례대로 저장되어야 하는 데이터입니다. 즉, 순서가 굉장히 중요한 데이터이므로 Array 같이 순서를 보장해주는 자료구조를 사용하는 것이 좋습니다. Array를 사용하지 않고 순서가 없는 자료 구조를 사용하는 경우에는 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어 들이고 비교해야 하는 번거로움이 발생합니다.

---

2. List (리스트)

: 배열의 문제점을 해결하기 위한 자료구조, 빈틈없는 데이터의 적재라는 장점을 가진다.

원소를 삭제했을 때 삭제된 데이터 뒤 원소로 빈틈없이 연속적으로 위치시킨다.

 

** List 특징

• 리스트의 핵심은 원소들 간의 순서로 순서가 있는 데이터의 모임이 리스트이며 리스트를 다른 이름으로 시퀀스(sequence)라고도 부른다.
• 배열에서 인덱스는 유일무이한 식별자이지만 리스트에서는 몇 번째 데이터인지 정도의 의미를 가진다.
• 빈 엘리먼트는 허용하지 않는다.
• 순차성을 보장하지 못하기 때문에 spacial locality 보장이 되지 않아 cash hit가 어렵다.
  
  

ArrayList와 LinkedList는 구현 방법에 따라 나뉜다.

• ArrayList
  • 배열을 이용해 리스트를 구현한 것
  • 접근이 빠름(순차 x) 하지만 데이터 추가와 삭제가 느림
  • 동적으로 사용하기 힘듬(결국 배열이므로 길이가 고정됨)
• LinkedList
  • 연결로 구현한 리스트
  • 한 원소에서 값과 다음 원소의 주소를 알고 연결하는 방식
  • 순차적으로 접근함 O(n)
  • 삽입, 삭제는 O(1)이지만 해당 지점까지 접근해야하므로 O(n)일 수 있음
  • → 배열과 다르게 논리적 저장 순서와 물리적 저장 순서가 일치하지 않는다!

 

면접 질문!

? ? Array와 ArrayList의 차이점

: Array는 크기가 고정적이고, ArrayList는 크기가 가변적입니다. Array는 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르고, ArrayList는 데이터 추가 및 삭제 시 메모리를 재할당하기 때문에 속도가 Array보다 느립니다.

---

3. HashTable (해쉬 테이블)

: (Key, Value)로 데이터를 저장하여 빠르게 데이터를 검색한다.

Key 값을 해시함수를 사용하여 변환한 값을 index로 삼는다.

 

* 해싱 : 해시 함수를 사용해 Key 값을 index로 변환하는 과정

* 해시 함수(Hash Fucntion)

: 해시 함수의 가장 중요한 점은 고유한 인덱스를 만드는 것.

: 만약 중복되는 인덱스가 발생한다면 충돌 발생!  따라서 해시 함수를 구현하는 해시 알고리즘을 적절히 구현해야 함.

 

** HashTable 특징

• 빠름 :  key - value의 1대1 매칭 구조라 삽입, 삭제, 검색 모두 평균적으로 (충돌X) O(1)의 시간 복잡도를 가짐
• 공간 효율성 낮음 : 데이터가 저장되기 전에 미리 공간을 만들어야되기 때문.
• hash function의 의존도가 높음 : hash function이 복잡하다면 hash를 만들어내는데 시간이 많이 소모
• 순서 보장 X : index를 hash function이 정하기 때문에 배열처럼 순차적인 index를 보장하지 않음
• 최악의 경우 ( 같은 인덱스에 모든 키값과 데이터가 저장된 경우 = 전부 충돌한 경우 ) O(key의 개수) 즉 O(n)의 시간 복잡도 가짐

 

면접 질문 !

? ? Hash Map과 Hash Table의 차이점

: 동기화 지원 여부와 null 값 허용 여부의 차이가 있다.

* 해시 테이블(Hash Table) : 병렬 처리를 할 때 (동기화를 고려해야 하는 상황) Thread-safe 하며 Null 값을 허용하지 않는다.

* 해시 맵(Hash Map) : 병렬 처리를 하지 않을 때 (동기화를 고려하지 않는 상황) Thread-safe 하지 않으며 Null 값을 허용한다.

? ? Hash Table과 시간 복잡도

: 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다. 빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문입니다. 각 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간 복잡도로 데이터를 조회합니다. 하지만 index값이 충돌이 발생한 경우 연결된 리스트들까지 검색해야 하므로 O(N)까지 증가할 수 있습니다.

---

4. Queue (큐)

: 선입선출(FIFO, First in first out) 방식의 자료구조

** Queue 특징

• 장점
  • 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 유리하다.

• 단점
  • 크기가 제한적이다.
  • 큐의 앞 부분이 비어도 데이터를 삽입할 수 없다.
  • 큐가 Empty여도 Not Empty라 판단할 수 있다. (rear가 맨 뒤에 있을 경우)

면접 질문 !

? ? Priority Queue (우선순위 큐)란?

: 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조 우선순위 큐 구현 방식에는 배열, 연결 리스트, 힙이 있고, 그중 힙 방식이 worst case라도 시간 복잡도 O(logN)을 보장하기 때문에 일반적으로 완전 이진트리 형태의 힙을 이용해 구현함.

---

5. Stack (스택)

: 후입선출(LIFO, Last-In-First-Out) 방식의 자료구조

 

** Stack 특징

• 스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.
• 스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다.

• 장점
  • 구현이 쉽다.
  • 원하는 데이터의 접근 속도가 빠르다.
  • 만약 내가 원하는 데이터가 배열의 3번째 위치에 있으면 arr[2]를 사용한다면 한번에 접근이 가능하기 때문이다.

• 단점
  • 데이터 최대 개수를 미리 정해야 한다.
  • 또한 데이터의 삽입과 삭제에 있어 매우 비효율적이다.