자료구조 - 리스트(배열)

[리스트]

리스트는 자료를 정리하는 방법 중 하나입니다.

리스트에는 항목이 차례대로 저장되어 있고, 리스트의 항목은 순서 또는 위치를 가집니다.

 

리스트에서 가능한 연산으로는

• 리스트에 새로운 항목을 추가한다(삽입 연산).
• 리스트에서 항목을 삭제한다(삭제 연산).
• 리스트에서 특정한 항목을 찾는다(탐색 연산).

이 있습니다.

 

 

[리스트의 추상 자료형(ADT)]

객체 : n개의 element 형으로 구성된 순서 있는 모임
연산 :
    insert(list, pos, item) ::= pos 위치에 요소를 추가
    insert_last(list, item) ::= 맨 끝에 요소를 추가
    insert_first(list, item) ::= 맨 처음에 요소를 추가
    delete(list, pos) ::= pos 위치에 요소를 제거
    clear(list) ::= 리스트의 모든 요소를 제거
    get_entry(list, pos) ::= pos 위치에 요소를 반환
    get_length(list) ::= 리스트의 길이를 구함
    is_empty(list) ::= 리스트가 비었는지 검사
    is_full(list) ::= 리스트가 꽉 찼는지 검사
    print_list(list) ::= 리스트의 모든 요소를 표시

 

 

[리스트의 구현]

리스트는 배열과 연결 리스트를 사용해서 구현할 수 있습니다. 

 

배열로 구현할 시 장점 & 단점

장점 : 구현이 간단하고 속도가 빠르다. 

단점 : 리스트의 크기가 고정된다.

 

리스트로 구현할 시 장점 & 단점

장점 : 리스트의 중간에 요소를 삭제 및 삽입하는 과정이 편리하다.

단점 : 구현이 복잡하고, 임이의 항목을 추출할 경우 배열보다 시간이 오래 걸린다.

 

 

 

[배열로 구현된 리스트]

배열을 사용하여 리스트를 구현하면, 연속적인 메모리 공간을 사용하여 데이터를 저장하게 됩니다.

 

 

항목 추가 연산

시간 복잡도 : O(n)

배열 끝에 욧소를 추가하면 O(1)의 시간이 소요되지만, 지정된 위치에 요소를 삽입하려면 그 위치 이후의 모든 요소를 오른쪽으로 이동해야하므로 최악의 경우 O(n)의 시간이 소요됩니다.

 

    void insert(int index, int element) 
    {
        if (index < 0 || index > length || length == MAX_SIZE) 
        {
            std::cout << "Index out of bounds or List is full\n";
            return;
        }
        for (int i = length; i > index; i--) 
        {
            arr[i] = arr[i - 1];  // 요소를 오른쪽으로 이동
        }
        arr[index] = element;  // 새 요소 삽입
        length++;  // 리스트 크기 증가
    }

 

 

 

항목 삭제 연산

시간 복잡도 : O(n)

지정된 위치의 요소를 삭제하려면 그 위치 이후의 모든 요소를 왼쪽으로 이동해야 하므로 최악의 경우 O(n)의 시간이 소요됩니다.

void remove(int index) 
{
        if (index < 0 || index >= length) 
        {
            std::cout << "Index out of bounds\n";
            return;
        }
        for (int i = index; i < length - 1; i++) 
        {
            arr[i] = arr[i + 1];  // 요소를 왼쪽으로 이동
        }
        length--;  // 리스트 크기 감소
    }

 

 

 

배열로 리스트를 구현하는 코드

#include <iostream>
#define MAX_SIZE 100  // 리스트의 최대 크기 정의

class ArrayList 
{
    private:
        int arr[MAX_SIZE];  // 배열을 사용한 리스트
        int length;         // 현재 리스트의 크기

    public:
        // 생성자: 공백 리스트 생성
        ArrayList() : length(0) {}

        // 리스트가 비어있는지 확인
        bool isEmpty() { return length == 0; }

        // 리스트의 크기 반환
        int size() { return length; }

        // 지정된 위치에 요소 삽입
        void insert(int index, int element) 
        {
            if (index < 0 || index > length || length == MAX_SIZE)
            {
                std::cout << "Index out of bounds or List is full\n";
                return;
            }
            for (int i = length; i > index; i--) 
            {
                arr[i] = arr[i - 1];  // 요소를 오른쪽으로 이동
            }
            arr[index] = element;  // 새 요소 삽입
            length++;  // 리스트 크기 증가
        }

        // 지정된 위치의 요소 삭제
        void remove(int index)
        {
            if (index < 0 || index >= length) 
            {
                std::cout << "Index out of bounds\n";
                return;
            }
            for (int i = index; i < length - 1; i++)
            {
                arr[i] = arr[i + 1];  // 요소를 왼쪽으로 이동
            }
            length--;  // 리스트 크기 감소
        }

        // 지정된 위치의 요소 반환
        int get(int index) 
        {
            if (index < 0 || index >= length) 
            {
                std::cout << "Index out of bounds\n";
                return -1;  // 오류 값 반환
            }
            return arr[index];
        }        

    // 리스트 출력 (디버깅 용도)
    void display() {
        for (int i = 0; i < length; i++) {
            std::cout << arr[i] << " ";
        }
        std::cout << std::endl;
    }
};

int main() 
{
    ArrayList list;
    list.insert(0, 1);
    list.insert(1, 2);
    list.insert(2, 3);
    list.display();

    list.remove(1);
    list.display();

    std::cout << "Element at index 1: " << list.get(1) << std::endl;

    return 0;
}