Coding/알고리즘

[자료구조] 순차 리스트 (Sequential List, Array List)

Dev_Klare 2023. 11. 25. 20:22

List - 리스트

  • 데이터들을 정해진 순서대로 일렬로 나열한 것
  • 리스트의 구현 방법에 따라 크게 순차 리스트, 연결 리스트로 나뉨
  • 해당 글에서는 순차 리스트만을 다룸

원소(데이터)들을 순서대로 나열해 둔 자료구조를 '리스트'로 정의할 수 있다.

흔히 '버킷 리스트(Bucket List)', '체크 리스트 (Check List)'와 같이 1번 ~~~, 2번 ~~~ 의 형태로 정리되어 있는 것을 생각할 수 있는데, 컴퓨터의 자료구조에서도 비슷하게 작동한다.

1번 원소, 2번 원소, 3번 원소.... 와 같은 순차적으로 정의되어 있는 원소들을 하나로 묶어둔 것을 '리스트'라고 합니다.

 

'배열'과 '리스트'는 혼동할 수 있지만 다른 개념입니다.

'배열'은 자료형 (Data Type)의 이름이고, '리스트'는 자료구조 (Data Structure)의 이름입니다.

 

Sequential List - 순차 리스트

해당 글에서는 순차 리스트에 대하여 집중적으로 다루도록 한다.

순차 리스트는 대게 배열 기반 리스트(Array List)라고도 부르며, 이름 그대로 자료형의 배열을 활용하여 구현하는 경우가 많다.

 

순차 리스트는 일렬로 놓여있는 의자에 사람이 앉는 것과 비슷하다.

의자에 미리 순서대로 번호를 붙여놓고, 사람들이 가서 앉으면 그 이후부터 의자의 번호로 사람을 부를 수 있는 것이다.

A라는 사람이 1번 의자에 앉았다면, 앞으로 A를 찾을 때는 1번 의자에 앉은 사람을 찾으면 된다. (인덱스 임의 접근)

2번 자리에 X라는 사람이 와서 앉아야 한다면, 2번 의자에 앉아 있던 사람부터 그 뒤쪽의 사람들이 모두 한 칸씩 뒤로 밀려나야 한다. (삽입)

만약 A가 자리를 뜬다면 그다음 번호 의자에 앉아 있던 사람들이 모두 앞으로 한 칸씩 당겨 앉아야 한다. (삭제)

관련 용어 정리

원소(Element) - 리스트의 각 데이터. 요소, 자료, 데이터와 동일.

인덱스(Index) - 리스트의 각 요소를 지칭하는 번호. N번째 요소에서 N을 인덱스라고 함. 말 뜻 그대로 데이터의 색인 역할을 함

특징

  1. 자료의 논리적인 순서(구조)와 물리적인 순서(구조)가 동일하다.
  2. 삽입, 삭제, 수정 등의 연산 이후에도 원소들 간의 순서의 변화가 없다.

1. 메모리 공간을 순차적으로 할당하여 구현하기 때문에 자료가 저장되어 있는 물리적인 순서와 자료에 접근하는 논리적인 순서가 동일하다. 논리적으로 첫 번째 원소는 실제 구조적으로도 첫 번째 데이터인 것이다.

2. 원소 1개가 삽입되었다고 해당 부분을 제외한 나머지 원소들의 상대적인 순서가 변하지 않는다.

장점

  1. 데이터의 임의 접근(직접 접근)이 가능하다.
  2. 간단하게 구현할 수 있다.

1. 데이터 별로 그 순서에 따라 인덱스라고 하는 번호가 부여하여, 인덱스를 통하여 데이터의 임의 접근이 가능하다. 이는 특수한 상황에서 탐색 과정을 거치지 않고 데이터에 직접 접근하게 해 주기 때문에 코드의 실행 시간 향상에 도움을 줄 수 있다.

2. 복잡한 과정 없이 데이터를 그저 순서대로 나열하는 것이기 때문에, 자료의 전처리 없이 간단하게 구현이 가능하다.

 

단점

  1. 데이터의 삽입, 삭제가 있는 경우 물리적인 데이터의 이동이 필요하다.
  2. 리스트의 크기가 미리 결정되어 있다.

1. 논리적인 순서와 물리적인 순서가 동일하기 때문에, 논리적인 순서의 변경이 필요한 경우가 있다면 물리적인 순서의 변경이 동반되어야 한다. 이는 자료의 삽입과 삭제가 자주 일어나는 경우 코드의 실행 시간이 상승하는 원인이 될 수 있다.

2. 언어와 실제 구현된 방법에 따라 상이할 수 있지만, 배열을 기반으로 생성된 Array List의 경우 선언과 동시에 크기가 고정되기 때문에 상황에 따라 메모리가 낭비되거나 오히려 부족한 경우가 발생할 수 있다.

데이터 다루기

위에서 의자 앉기를 예시로 들었던 것처럼, 리스트의 데이터를 다루기 위해서 비슷한 과정을 거쳐야 한다.

탐색

리스트는 인덱스를 통해 자료에 직접적인 접근이 가능하다.

 

하지만, 만약 원소들의 순서에 논리적인 규칙이 없이 단지 임의 순서만 존재하는 경우, 원하는 원소를 탐색하기 위해서 리스트의 처음부터 원하는 원소를 찾을 때까지 리스트 내의 원소를 확인해야 한다.

삽입

리스트에 자료를 삽입하기 위해서는 자료가 들어갈 자리를 먼저 만들어주어야 한다.

이때 리스트는 논리적 순서와 물리적 순서가 동일해야 하기 때문에, 논리적 순서를 맞춰주기 위해 물리적 순서를 맞춰주기 위해 논리적 순서의 수정이 필요한 데이터 모두 메모리 상의 물리적 이동이 필요하다.

 

삭제

삽입과 마찬가지로 삭제된 데이터의 빈자리를 나머지 데이터로 채워야 하기 때문에, 데이터의 메모리 이동이 필요하다.

앞 인덱스의 데이터가 삭제되었다면, 뒤의 모든 데이터가 앞으로 자리를 옮겨야 한다.

 

구현

Array List라고 불리는 것처럼, 배열 자료형을 활용하여 간단하게 구현할 수 있다.

※ 자료구조의 구현 방법은 코드 제작자에 따라 다르기 때문에 참고용으로만 봐주시기 바랍니다.

#include<iostream>
using namespace std;
int main(){
    char List[7]={'A','B','C','D','E','F'};
    
    // 데이터 탐색
    cout<<"0번 인덱스의 원소값 : "<<List[0]<<'\n';
    cout<<"3번 인덱스의 원소값 : "<<List[3]<<"\n\n";
    
    // 데이터 삽입 (3번 인덱스에 G를 삽입)
    cout<<"삽입 전 3번 인덱스의 원소 : "<<List[3]<<'\n';
    for(int i=6; i>3; i--)
        List[i]=List[i-1];
    List[3]='G';
    cout<<"삽입 후 3번 인덱스의 원소 : "<<List[3]<<"\n\n";
    
    // 데이터 삭제 (3번 인덱스의 원소를 삭제)
    cout<<"삭제 전 3번 인덱스의 원소 : "<<List[3]<<'\n';
    for(int i=3; i<6; i++)
        List[i]=List[i+1];
    List[6]='\0';
    cout<<"삭제 후 3번 인덱스의 원소 : "<<List[3]<<"\n\n";
}

 

코드의 실행 결과

0번 인덱스의 원소값 : A
3번 인덱스의 원소값 : D

삽입 전 3번 인덱스의 원소 : D
삽입 후 3번 인덱스의 원소 : G

삭제 전 3번 인덱스의 원소 : G
삭제 후 3번 인덱스의 원소 : D

 

맺음말

리스트 자료구조는 Python의 list, C++의 vector 등을 활용하여도 간단하게 구현할 수 있고, 자주 사용되는 자료구조이다.

다음 글에서는 리스트 중 연결 리스트 Linked List에 대하여 소개하겠습니다.

저작자표시 비영리 변경금지 (새창열림)