[자료구조] Array list와 배열(Array) 개념과 장단점, 시간복잡도

1. List 자료구조 vs Set 자료구조

Set과 List는 둘 다 선형자료구조이지만 중요한 차이점이 있습니다.

 

(1) 중복된 요소

(2) 순서가 있는/없는

(3) 인덱스 기반 접근

 

(1) 중복 요소

- Set은 중복된 요소를 허용하지 않습니다. 각 요소는 유일해야 합니다.

- List는 중복된 요소를 허용합니다. 동일한 요소가 여러 번 포함될 수 있습니다.

 

(2) 순서

- Set은 인덱스 순서가 보장되지 않습니다. [1,2,3],[2,1,3], [3,1,2]가 각 인덱스와 값이 달라도 set에 들어가면 [1,2,3]으로 동일한 자료구조가 됩니다. 각 요소가 어떤 순서로 들어오든 상관없이 하나씩 존재한다는 점에서 모두 같은 set이 되는 것입니다. 요소들의 순서는 구현에 따라 다를 수 있습니다.

- List는 요소들이 순서에 따라 정렬됩니다. 요소들은 삽입 순서를 유지합니다.

[1,2,3], [2,1,3], [3,1,2] 모두 다른 리스트입니다.

 

(3) 인덱스 기반 접근

- Set은 인덱스를 사용하여 요소에 직접 접근할 수 있는 메커니즘을 제공하지 않습니다.

- List는 각 요소에 할당된 인덱스를 사용하여 요소에 직접 접근할 수 있습니다.

 

따라서, Set은 유일한 요소의 집합을 관리하거나 중복을 허용하지 않는 데이터를 처리할 때 유용합니다. List는 순서가 중요하거나 요소의 중복이 허용되는 상황에서 사용될 수 있습니다. 선택은 사용하는 데이터의 특성과 작업의 목적에 따라 달라집니다.

 

2. Array list vs Linked List

List 자료구조의 구현 방법은 두 가지입니다. Array List와 Linked List.

참고로 파이썬의 list는 Dynamic Array로 구현된 Array List입니다.

각각의 특징과 장단점을 살펴보겠습니다.

 

파이썬의 list는 Array list

• Array List는 내부적으로 배열(Array)을 사용하여 요소를 저장하는 자료구조입니다.
• 요소들은 연속적으로 메모리에 저장되며, 인덱스를 사용하여 접근할 수 있습니다.
• 배열의 크기는 처음에 지정되지만, 요소가 추가될 때 동적으로 크기를 조정할 수 있습니다.
• 장점 : 인덱스를 사용하여 임의의 위치에 접근하는 데에는 빠른 성능을 보입니다.
• 단점 : 요소의 삽입, 삭제가 비효율적일 수 있습니다. 배열의 크기를 조정해야 하거나, 중간에 요소를 삽입하거나 삭제할 경우 다른 요소들을 이동시켜야 하기 때문입니다.
• 일반적으로 데이터의 접근이 빈번하고, 삽입과 삭제가 상대적으로 적은 경우에 적합합니다.

 

파이썬의 list는 Array list이므로, linked list를 써야하면 따로 Node를 구성해서 직접 만들어주어야 한다.

• Linked List는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조입니다. 각각의 요소(Node)가 데이터 값과 다음 요소를 가리키는 포인터(next node의 주소값)로 구성된 자료구조입니다.
• 메모리에서 연속적으로 저장되지 않으며, 각 노드는 다음 노드의 주소를 참조하여 연결됩니다. 이렇게 각각의 node가 next node의 메모리 주소값을 가리킴으로써 논리적인 연속성을 갖게 됩니다.
• 장점 : 새로운 요소의 삽입과 삭제가 다른 요소들을 이동시키지 않아도 가능합니다. 단지 링크를 조정하면 되기 때문에 비교적 빠른 성능을 보입니다.
• 단점 : 임의의 위치에 접근하기 위해서는 처음부터 순차적으로 탐색해야 하기 때문에 접근 시간이 오래 걸립니다.
• 데이터의 삽입과 삭제가 빈번하게 일어나는 경우, 데이터의 순서가 자주 변경되는 경우에 적합합니다.

요약하자면, Array List는 인덱스를 사용한 임의의 접근과 데이터의 삽입/삭제가 적은 상황에 유리하며, Linked List는 데이터의 순서 변경과 삽입/삭제가 빈번한 상황에 유리합니다. 선택은 사용하는 상황과 필요한 작업에 따라 달라질 수 있습니다.

 

3. Array list 구현

파이썬 list는 Dynamic Array로 만들어진  Array list이다.

Array list는 Array로도 구현할 수 있고, Dynamic Array로도 구현할 수 있습니다.

그런데 Dynamic Array 또한 Array로 구현된 것입니다. 

 

(1) (배열) Array

배열은 선언시에 size를 정하여 해당 고정된 size 만큼의 연속된 메모리를 할당 받아 data를 연속적/순차적으로 저장하는 자료구조입니다.

int arr[4] ={1,2,3,4};

 위의 c언어 예시에서 배열 size를 5로 정했기 때문에 int형 데이터 (4byte)를 4개 저장할 메모리 공간인 16 byte를 미리 할당 받습니다. 이처럼 고정된 size를 가지게 되므로 static array라고도 부릅니다.

 

 메모리 구조에서, 메모리 하나하나의 데이터를 비트로 저장하고 이 비트가 8개 모인 Byte고, byte마다 주소가 주어집니다. int형 데이터는 4byte 이기 때문에 아래 캡처와 같이 4개의 byte를 할당받을 것입니다. 

int형 배열의 크기가 총 4면, 4byte씩 4개를 연이어서 할당받을 것입니다. 

C언어에서는 이러한 주소값을 1바이트 크기의 메모리 공간으로 나누어 표현하고,

int형 데이터는 4바이트의 크기를 가지지만, int형 데이터의 주소값은 시작 주소 1바이트만을 가리키기 때문에 각 원소에 접근하고 싶다면 각 원소가 저장된 첫번째 주소로 찾아가면 됩니다. 배열 변수는 자신이 할당받은 메모리의 첫번째 주소를 가리킵니다.

첫 주소값만 알고 있다면 어떤 index에도 즉시 접근 가능합니다.

이것이 Arr[1]으로 접근하는 것과 Arr[0] + 4 btye로 접근하는 것이 같을 수 있는 원리입니다.

위 캡처에서 4에 접근하고 싶다면 첫번째 주소에서 4바이트만큼 3번 떨어져 있는 주소로 가면 됩니다. 

일반화하자면, 첫번째 데이터가 저장된 주소값 + 4 * n을 하면, 바로 n 인덱스에 접근할 수 있게 됩니다. 아무리 긴 배열이더라도 이 한번의 연산으로 원하는 데이터에 바로 접근할 수 있기 때문에 O(1)의 시간복잡도를 가지게 됩니다.

( linked list는 메모리 상에서 연속적/순차적으로 저장되어 있지 않기 떄문에 이러한 direct(random) access는 불가능합니다. n 번째 데이터에 접근하기 위해서 array는 1번의 연산만 해도 되지만 O(1), linked list는 n 번의 연산을 해야하기 때문에 시간복잡도는 O(n)이 됩니다.

 

장점 : 데이터의 갯수가 정해져 있는 경우

단점 : 선언 시에 정한 size보다 더 많은 데이터를 저장해야 하는 경우 공간이 남아있지 않을 수 있습니다. 그렇다고 매번 크기가 엄청 큰 배열을 선언한다면 그만큼 메모리 비효율이 발생하게 됩니다. 이러한 문제점을 해결할 수 있는 것이 바로 dynamic array입니다.

(2) Dynamic Array

선언 size를 변경할 수 없는 정적 배열과 다르게 동적 배열은 size를 늘릴 수 있습니다.

즉, 동적 배열은 배열의 크기(size)를 변경(resize)할 수 있는 배열입니다. 동적 배열에 데이터를 계속 추가하다가 기존에 할당된 size를 초과하게 되면, size를 늘린 배열을 새로 선언하고 그곳으로 모든 데이터를 옮깁니다. 그리고 기본의 배열은 메모리에서 삭제(free)합니다. 이 과정을 resize라고 합니다. resize를 한칸씩 늘린다면 비효율적이므로 일반저그로 2배 큰 크기로 resize 합니다. 이를 더블링(Doubling)이라고 합니다. 이러한 resize 덕분에 데이터를 추가 저장할 수 있게됩니다.

시간복잡도는 기존에 배열에 O(1)으로 바로바로 추가 가능하고(배열이 남아있을 때), 배열이 꽉 찼을 때는 기존 배열 보다 더 큰 배열을 할당받는 resize 과정(기본적으로는 2배 더 큰 배열을 할당함)을 통해 기존 배열에 있던 데이터들을 하나하나 옮겨 적으므로 (O(n))입니다. 그 후, 원래 추가하려던 데이터를 추가합니다. 그 다음 기존의 배열은 삭제하게됩니다. 

 

선언시에 배열의 크기르 정하지 않아도 되기 때문에 코딩테스트에서 이 dynamic array를 자주 사용하게 됩니다. python에서는 list 자료형을 통해 dynamic array를 이미 잘 구현해두었기 때문에 직접 구현할 필요없이 사용할 수 있습니다.

코딩테스트 문제에서 배열을 사용해야 하는 경우 파이썬은 list(Array list(dynamic array))를 선언하여 사용하면 됩니다.

 

4. 파이썬 list의 연산(operation)들과 시간복잡도

 

https://www.youtube.com/watch?v=PEnFFiQe1pM 배열에서 단순 추가는 O(1), 임의 삽입/삭제는 O(n), 맨뒤 추가/삭제는 O(1)

마지막 데이터 삽입/삭제가 O(1)인 이유는, 배열의 size를 알고 있기 때문에 맨 마지막 인덱스를 알 수 있어서 이에 접근하는 것은 O(1)로 충분하기 때문입니다.

중간 삽입/삭제이 O(n)인 이유는 배열이 연속적으로 저장이 되어야 하기 때문에 삽입을 원하는 인덱스를 비우고 해당 인덱스부터 기존에 있던 원소들을 한칸씩 뒤로 미루어야 하기 때문입니다. 이 한칸씩 옮기는 작업은 중간에 삭제하는 경우도 마찬가지 입니다.

배열(Array)에서 처음 삽입/삭제하는 것의 시간 복잡도는

 

1) 처음에 삽입하는 경우: 배열의 처음에 요소를 삽입하려면, 기존의 모든 요소를 오른쪽으로 한 칸씩 이동시켜야 합니다. 이는 모든 요소를 이동시키므로 최악의 경우 배열의 크기에 비례하는 시간이 걸립니다. 처음에 삽입하는 경우의 시간 복잡도는 O(n)입니다. (n은 배열의 크기)

 

2) 처음에 삭제하는 경우:배열의 처음에서 요소를 삭제하면, 삭제된 요소 이후의 모든 요소를 왼쪽으로 한 칸씩 이동시켜야 합니다. 마찬가지로, 모든 요소를 이동시키므로 최악의 경우 배열의 크기에 비례하는 시간이 걸립니다. 따라서, 처음에 삭제하는 경우의 시간 복잡도도 O(n)입니다. (n은 배열의 크기)

 

결론적으로, 배열에서 처음에 삽입/삭제하는 경우의 시간 복잡도는 모두 O(n)입니다. 이는 배열의 크기에 비례하여 연산이 수행되는 것을 의미합니다. 따라서 만약 자주 처음에 삽입하거나 삭제해야 하는 경우에는 다른 자료구조, 예를 들어 연결 리스트(Linked List)를 고려해볼 수 있습니다. 연결 리스트는 삽입과 삭제에 특화되어 있어, 해당 연산의 시간 복잡도가 O(1)이기 때문입니다.

 

동적 배열에서 마지막 위치에서 요소를 삭제하는 경우에는 단순히 해당 요소를 삭제하므로 추가적인 요소 이동이 필요하지 않습니다. 따라서 삭제 작업은 O(1)의 시간 복잡도를 가집니다.

 

동적 배열의 크기를 조정해야 한다면, 크기 조정 연산에 따른 시간 복잡도도 고려해야 하므로, 일반적으로 동적 배열에서 크기 조정은 O(n)의 시간 복잡도를 가집니다.

 

5.  리트코드 : array 리스트 풀이

https://leetcode.com/problems/design-browser-history/

Design Browser History - LeetCode

1472. Design Browser History

 

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Implement the BrowserHistory class:

• BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
• void visit(string url) Visits url from the current page. It clears up all the forward history.
• string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
• string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

Constraints:

• 1 <= homepage.length <= 20
• 1 <= url.length <= 20
• 1 <= steps <= 100
• homepage and url consist of  '.' or lower case English letters.
• At most 5000 calls will be made to visit, back, and forward.

class BrowserHistory(object):
    def __init__(self, homepage):
        self.li = [homepage]
        self.index = 0

    def visit(self, url): #append
        if self.index < len(self.li)-1:
            for i in range(self.index+1, len(self.li)):
                self.li.pop()
        self.li.append(url)
        self.index += 1

    def back(self, steps): #앞 인덱스
        if self.index > steps:
            self.index -= steps
        else:
            self.index = 0
        return self.li[self.index]

    def forward(self, steps): # 뒤 인덱스
        if len(self.li)-1 < self.index + steps:
            self.index = len(self.li) -1
        else:
            self.index += steps
        return self.li[self.index]