자료구조, 배열과 리스트에 대한 이해

1. 자료구조 (Data Structure)

• 데이터를 표현하고 저장하는 방법
• 데이터의 흐름과 밀접한 관련이 있다.
  • 예, FIFO, LIFO, 우선순위 처리 등

2. 왜 자료구조가 중요한가?

• 프로그램은 크게 자료(Data)와 명령으로 구성되어 있다. 프로그램의 자료를 효율적으로 저장할 때, 메모리(저장 공간)를 절약할 수 있고, 수행(실행) 시간을 단축시킬 수 있다.
• 따라서 프로그램의 수행 시간 혹은 저장 공간을 고려하여 자료 구조를 설계할 수 있어야 한다.
  • 그리고 이들을 고려하기 위해 프로그램의 목적이 무엇인지, 기능이 무엇인지 살펴봐야 한다.
  • 예) 윈도우 탐색기 -> 폴더 구조(트리)와 파일 목록(리스트)

    Ref. [자료구조] #01 1장 - 자료구조의 시작 - 프리렉

3. 자료구조의 종류

• 단순 구조는 프로그래밍 언어에서 제공하는 기본 데이터 타입을 말한다.

  • 정수
  • 실수
  • 문자
  • 문자열

• 선형 구조는 자료들 사이의 앞뒤 관계가 일대일(1:1) 로 구성된다.

  • 리스트
  • 스택
  • 큐
  • 덱
    

    Ref. [자료구조] #01 1장 - 자료구조의 시작 - 프리렉

• 비선형 구조는 자료들 사이의 앞뒤 관계가 계층 구조 혹은 망 구조로 이루어진다.

  • 트리
  • 그래프
    

    Ref. [자료구조] #01 1장 - 자료구조의 시작 - 프리렉

• 파일 구조는 보조기억장치(HDD 등)에 저장되는 파일에 대한 자료구조를 말한다.

  • 순차파일
  • 색인파일
  • 직접파일

4. 추상 자료형

• 추상 자료형(Abstract Data Type, ADT): 자료구조를 표현하는 가장 대표적인 방법 중 하나

• 자료구조를 사용할 수 있는 인터페이스를 정의한다. (혹은 자료구조의 연산들을 정의)

• 어떻게(How) 구현이 이루어지는 지를 정의하지 않고, 무엇(What)인지를 정의한다.

• 정보 은닉의 특징을 가진다.

  • 정보 은닉: 중요한 정보만 나타내고, 중요하지 않은 정보는 숨기는 것

    

    Ref. [자료구조] #01 1장 - 자료구조의 시작 - 프리렉

• 이미지 속에서 개발자 B는 자료구조의 내부 구현 로직은 알지 못하더라도, 인터페이스를 통해 자료 구조를 사용할 수 있다.
  

  Ref. [자료구조] #01 1장 - 자료구조의 시작 - 프리렉

5. 배열

• 같은 자료형의 데이터를 메모리상에 연속적으로 저장하는 자료형

일차원 배열

Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

• 원칙적으로는 배열은 변수를 초기화한 후에 사용해야 한다.

  • 디버그 중에는 별 문제가 되지 않지만, 릴리즈 시 에러가 발생하기 때문
  • 초기화시 배열의 크기가 필요하다. (초기화 리스트를 사용하면 불필요)

• 두 가지 방식의 초기화 방법

  • 선언과 동시에 배열 초기화
  • 선언 이후 별도의 값 설정
    

    Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

• 문자열 배열의 경우

  • 아래 (방법 2)에서처럼 {0, }으로 초기화하지 않을 경우, 문자열 마지막에 널 문자(\0) 추가하는 것을 깜빡할 수 있다. 즉, str[5] = '\0'를 잊어버리면 릴리즈시 문제가 발생한다.
    

  Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

다차원 배열

• 배열의 원소가 배열 자료형인 배열

  • 예) 2차원 배열의 각 원소는 1차원 배열이다.
    

    Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

• 다차원 배열 배열의 초기화 방식

  • 다차원 배열의 행은 열보다 우선한다. (row가 먼저 오고, col이 그 다음)
  • 메모리가 저장되는 방식은 선형 방식(앞뒤가 일대일 관계)을 유지한다.
    

  Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

배열의 특징과 한계

• 인덱스를 가짐: 한 번 부여된 Index는 변경되지 않음
• 데이터를 메모리에 순차적으로 저장
• 인덱스를 통해 데이터의 빠른 조회가 가능
• 크기가 고정되어 있음: append, remove와 같이 데이터를 추가하거나 삭제하는 방법이 따로 존재하지 않음
• 데이터에 대한 인덱스의 값이 고정되어 삭제된 엘리먼트의 공간이 그대로 남아있게 됨 → 데이터 낭비
• 이러한 한계를 보안한 새로운 자료 구조 → List

  Ref. 스터디 6주차 : 자료구조 - 배열과 링크드리스트 - 유지님 노션

6. 리스트

리스트의 개념

• 자료를 순서대로 저장하는 자료구조를 말한다.

• 일직선으로 연결된(Sequential) 자료

  

  Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

배열과 리스트는 다르다!

- 예를 들어, 아래 그림의 중간에서처럼 파일 목록 중 하나가 삭제되었다고 생각해보자. 배열과 달리 리스트의 경우, 중간이 비어있으면 안 된다. (리스트는 요소끼리 서로 연결되어 있어야 한다.) 따라서 제거된 파일 다음의 요소들을 한 칸씩 위로 올려야 한다.
- 또 하나, 마지막 부분에서처럼 새로운 파일이 목록 중간에 하나 추가되었다고 해보자. 배열은 해당 인덱스의 값을 덮어쓰지만, 리스트는 해당 인덱스부터 한 칸씩 뒤로 밀려나고 새로운 파일이 중간에 추가된다.

Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

사용 예

• 문자 리스트(문자열, String)
• 문자열 리스트
• 행렬(Matrix)
• 다항식
  
  
  

  Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

리스트 추상 자료형

• 리스트 생성
  • 최대 원소 개수 n
• 원소 추가
  • 원소 추가 가능 여부 판단
• 원소 반환
• 원소 제거
  • 리스트 초기화
• 리스트 삭제

Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

배열 리스트 (ArrayList)

• 배열을 이용하여 구현된 리스트

• 논리적 (저장) 순서와 물리적 (저장) 순서가 동일하다.

• 원소의 위치 인덱스는 0부터 시작한다. (배열과 동일)

• 배열과 다르게 모든 자료가 일직선으로 연결되어 있어야 한다. (중간에 자료가 끊기면 안 된다.)
  

  Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

• 배열 리스트의 원소 추가

  배열과 달리 배열 리스트는 원소를 중간에 추가할 수 있다.

  • 원소를 추가하기 전 기존 원소들을 한 칸씩 이동하는 연산이 필요하다.

    • 시작 위치와 방향, 그리고 어디까지 이동시킬 건지를 파악해야 한다.
    • 아래 그림에서는 마지막 원소 4부터 시작해서 왼쪽 방향으로 인덱스 1(내가 추가하기 원하는 자리)까지의 원소들을 이동시킨다.
      

    Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

• 배열 리스트의 원소 제거

  • 원소가 제거된 후 기존 원소들을 한 칸씩 이동시킨다.
    - 시작 위치와 방향, 그리고 어디까지 이동시킬 건지를 파악해야 한다.
    

  Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

질문

Q. 원소의 개수가 10만 개인 배열 리스트에서 원소의 추가/제거가 빈번하게 발생한다면?

A. 인덱스 0의 원소를 삭제한다면, (10만 - 1)개 만큼의 원소를 이동해야 한다. 이에 따르면 삭제하려는 원소와 관계없는 원소들까지 이동시켜줘야 하는 불편함이 생긴다.

링크드 리스트 (LinkedList)

• 연결 리스트라고도 불리며, 연결 포인터를 이용하여 구현한다.

• 배열 리스트와 달리 논리적 (저장) 위치만 순차적이고, 물리적 (저장) 위치는 순차적이지 않을 수 있다. (최대 원소 개수 지정에서 차이가 발생한다.)
  

  Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

• 연결 리스트를 구성하는 기본 단위는 노드이다.

  • 노드: 자료(Data) + 링크(Link)

  • 연결 리스트에서 노드의 추가와 제거는 링크의 추가와 제거를 의미한다. (배열 리스트에서는 원소의 이동이 곧 추가와 제거를 의미)
    

    Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

• 연결 리스트의 노드 추가

  • 예) 인덱스 1에 새로운 원소 5를 추가
    

    Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

• 연결 리스트의 노드 제거

  • 예) 인덱스 2의 원소 제거
    

    Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

연결 리스트의 종류

Ref. [자료구조] #04 2장 - C의 단순 자료형/배열

• 단순 연결 리스트(Singly Linked List)
• 원형 연결 리스트(Circular Linked List)
  • 순환 구조
• 이중 연결 리스트(Double Linked List)
  • 노드들이 양방향으로 연결되어 있음
    • 장점: 이전 노드에 바로 접근이 가능하다.
    • 단점: 이전 링크를 추가하기 때문에 메모리가 추가적으로 필요하다.

배열 리스트 vs 연결 리스트

• 연결 리스트의 장점 (배열 리스트의 단점)

  • 원소 추가/제거시 불필요한 원소 이동이 필요없다. 단순히 노드 사이에 링크를 붙였다 떼어줬다 하면 된다.
  • 배열을 쓰지 않기 때문에 배열의 크기를 고려하지 않아도 된다. (즉, 최대 원소 개수를 제공하지 않아도 됨)

• 연결 리스트의 단점 (배열 리스트의 장점)

  • 포인터를 많이 사용해야 하므로 구현하기가 조금 더 어렵다.
  • 탐색시 시간이 좀 더 필요하다.
    • 배열 리스트는 논리적 저장 위치가 물리적 저장 위치와 일치하기 때문에 인덱스를 사용하면 한 번에 원하는 인덱스의 원소를 찾을 수 있다. 하지만, 연결 리스트는 내가 원하는 인덱스를 찾으려면 처음 노드부터 차례대로 탐색해야 한다.
    • 따라서 원소의 개수가 N개일 때, 탐색에 걸리는 시간은 배열 리스트와 연결 리스트 각각 O(1), O(N)이다.

Ref. 스터디 6주차 : 자료구조 - 배열과 링크드리스트 - 유지님 노션

Refs

• CH1. 자료구조와 알고리즘의 이해 - Seongkyun Han's blog
• [자료구조] #01 1장 - 자료구조의 시작 - 프리렉
• [자료구조] #04 2장 - C의 단순 자료형/배열
• 스터디 6주차 : 자료구조 - 배열과 링크드리스트 - 유지님 노션