1️⃣

리스트 (List)

Array List

doubly linked list로의 확장

시간복잡도

↩︎ 뒤로 가기

리스트 (List)

List는 순서를 가지고 원소들을 저장하는 자료구조 입니다. sequence라고도 불립니다.

구현방법으로는 Array List로 구현할 수있고, Linked List로 구현할 수 있습니다. python에서 사용하는 list 자료구조는 Array List로 구현되었습니다.

Array List

배열을 기반으로 구성된 list 자료구조입니다. static array로 구현할 수 있고, dynamic array로도 구현할 수 있습니다.

배열 Static Array

배열의 특성

1. 고정된 저장 공간(fixed-size)

2. 순차적인 데이터 저장(order)

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

int arr[5] = {3, 7, 4, 2, 6} // size가 5인 int형 배열 선언
C
복사
Array 선언 in C언어

위의 예시에서는 배열의 size를 5로 정했기 때문에 int형 데이터(4 byte) 5개를 저장할 메모리 공간인 20 Byte를 미리 할당을 받습니다. 이처럼 고정된 size를 갖게 되기 때문에 static array라고 부르기도 합니다.

4byte(int형 데이터) * 5(size) = 20 byte

또한 배열의 데이터를 연속적이고 순차적으로 메모리에 저장합니다.

Random access

메모리에 저장된 데이터에 접근하려면 주소값을 알아야 합니다. 배열변수는 자신이 할당받은 메모리의 첫 번째 주소값을 가리킵니다. 배열은 연속적/순차적으로 저장되어 있기 때문에 첫 주소값만 알고 있다면 어떤 index에도 즉시 접근이 가능합니다. 이를 direct access 또는 random access라고 부릅니다. 첫 번째 데이터가 저장된 주소값이 0x4AF55라면 2번 째 데이터는 0x4AF55 + 4*1(byte)에 저장되어 있겠죠. 3번 째 데이터는 0x4AF55 + 4*2(byte)에 저장되어 있을 것이고, n번 째 데이터는 0x4AF55 + 4*(n-1)에 저장되어 있을 겁니다. 아무리 긴 배열이더라도 한번의 연산으로 원하는 데이터에 바로 접근할 수 있습니다. 즉 O(1)의 시간복잡도를 갖습니다.

다음에 배울 linked list는 메모리상에서 연속적/순차적으로 저장되어 있지 않기 때문에 random access는 불가능 합니다.

n

번 째 데이터에 접근하기 위해서 array는 1번의 연산으로 되지만(

O(1)

), linked list는

n

번의 연산을 해야 하기 때문에 시간복잡도는

O(n)

이 됩니다.

고정된 저장 공간

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

동적 배열 dynamic array

선언 이후에 size를 변경할 수 없는 정적배열(Static Array)과 다르게 동적배열(Dynamic Array)는 size를 늘릴 수 있습니다.

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

Dynamic Array 사용법

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

즉 문제에서 배열을 사용해야 하는 경우에는 list를 선언하여 사용하면 됩니다. 우리가 익혀야 할 것은 list의 연산(operation)들과 시간복잡도 입니다.

	Static array	Dynamic array
access / update	$O(1)$	$O(1)$
insert_back	$O(1)$	amortized $O(1)$
delete_back	$O(1)$	$O(1)$
insert_at	$O(n)$	$O(n)$
delete_at	$O(n)$	$O(n)$

이제 파이썬에서 리스트가 어떻게 선언되고 연산이 어떻게 이루어지는 지 알아보도록 합시다.

리스트의 선언

a = list()  
a = [1, 2, 3]
Python
복사

리스트 접근하기

•

0번째 원소 접근 하기

Python
복사

•

0번째 원소 업데이트 하기

Python
복사

리스트의 원소 추가

리스트의 원소 추가 같은 경우, 마지막에 원소를 삽입 하는 것과 중간에 원소를 삽입하는 것으로 나눌 수 있습니다.

•

마지막에 원소 추가

리스트의 마지막에 원소를 삽입하는 경우 맨 뒤에 원소를 추가하기만 하면 되어서

O(1)

의 시간복잡도를 갖습니다.

a.append(1)
Python
복사

•

중간에 원소 추가

하지만 리스트의 중간에 원소를 삽입하는 경우, 원소를 삽입한 후 뒤의 원소들을 한 칸 씩 미루어야기에

O(n)

의 시간복잡도를 갖습니다.

a.insert(2,10)
Python
복사

⇒ 2번째 index에 10을 추가한다

리스트 원소 삭제

리스트의 원소 삭제 역시, 마지막 원소를 삭제 하는 것과 중간 원소를 삭제하는 것으로 나눌 수 있습니다.

•

마지막 원소 삭제

리스트의 마지막 원소를 삭제하는 경우, 맨 뒤 원소를 삭제하기만 되기에

O(1)

의 시간복잡도를 갖습니다.

Python
복사

•

중간 원소 삭제

하지만 리스트의 중간 원소를 삭제하는 경우, 원소를 삭제한 후 뒤의 원소들을 한 칸씩 당겨야기에

O(n)

의 시간복잡도를 갖습니다.

Python
복사

⇒ 2번째 index에 있는 값을 삭제합니다.

a.remove(2)
Python
복사

⇒ a에서 제일 앞에 있는 값2를 찾은 후 삭제합니다

⇒ 만약에 a에 2가 없으면, error가 납니다

Linked List

Linked List Linked List는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조 입니다.

일단 Node는 데이터 값(value)과 다음 주소값(next)로 구성되어 있습니다.

Node의 구현

class Node :
    def __init__(self, value = 0, next = None):
        self.value = value
        self.next = next
Python
복사

물리적 비연속적, 논리적 연속적

Linked List는 메모리상에서는 비연속적으로 저장이 되어 있지만, 각각의 node가 다음 노드의 메모리 주소값을 가리킴으로써 논리적으로 연속성을 갖게 됩니다.

Array의 경우 연속성을 유지하기 위해 메모리 상에서 순차적으로 데이터를 저장하는 방식을 사용하였지만, Linked list에는 메모리 상에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유롭습니다.

Linked List구현

우리는 앞서서 linked list는 Node라는 구조체가 연결되는 형식으로 정의되는 자료구조라고 언급하였습니다. 그럼 이 노드들을 어떻게 연결 할 수 있을까요?

우선 아래와 같이 Node class를 활용해 여러 개의 node들을 만들어보도록 합시다.

class Node :
    def __init__(self, value):
        self.value = value
        self.next = None
Python
복사

first = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
Python
복사

그럼 현재 4개의 노드가 만들어진 상태입니다. 하지만 논리적 연결성은 아직까지 존재하지 않습니다.

논리적 연결성은 아주 쉽게 만들 수 있습니다.

first.next = second
second.next = third
third.next = fourth
Python
복사

이렇게 하여, 간단한 linked list가 완성 되었습니다. 위의 과정들을 LinkedList라는 class를 만들고, append(), remove()를 정의하면, 더욱 더 쉽게 linked list를 만들 수 있습니다.

기본적인 LinkedList의 클래스는 다음과 같습니다.

class LinkedList(object):
    def __init__(self):
        self.head = None
Python
복사

아주 간단하게 생겼습니다.

self.head는 링크드 리스트의 첫 번째 원소를 가르킵니다.

생성 초기에는 비어있으므로 None으로 설정해줍니다.

이제 linked list에서 원소들을 추가하는 함수 append를 볼 것입니다. append함수는 다음 2가지를 기억해야 합니다.

•

첫 번째 원소인 경우, head로 지정해주어야 합니다

•

노드를 추가할 때는 마지막 노드 다음에 추가해야 합니다.

class LinkedList(object):
    def __init__(self):
				self.head = None
    def append(self, value):
				new_node = Node(value)
        if self.head is None:
            self.head = new_node
        else:
            ptr = self.head
            while(ptr.next):
                ptr = ptr.next    
            ptr.next = self.current = new_node
Python
복사

저희가 앞서 만든 linked list를 위의 LinkedList를 통해 구현되는 과정을 보도록 합시다.

우선 링크드 리스트를 하나 만들어줘야 합니다.

linkedlist = LinkedList()
Python
복사

linkedlist.append(1)
Python
복사

first에 해당하는 new_node가 Node class에 의해서 만들어집니다.

현재 self.head가 None 임으로, 새로운 노드를 head가 가리키도록 해야 합니다.

이제 저희는 second 노드를 만들어줘야 합니다.

linkedlist.append(2)
Python
복사

second에 해당하는 new_node가 Node class에 의해서 만들어졌습니다.

현재 self.head가 None이 아님으로, else문으로 가야 합니다. 저희는 앞서 말했듯이 마지막 노드 다음에 new_node를 추가해줘야 합니다.

그런데 head인 first 노드는 이미 첫 번째 노드이자 마지막 노드입니다. 그렇기에 ptr.next 는 None 입니다.

따라서 while 반복문을 돌지 않고 ptr의 다음을 new_node로 연결해주면 됩니다.

이제 저희는 third 노드를 만들어줘야 합니다.

linkedlist.append(3)
Python
복사

third에 해당하는 new_node가 Node class에 의해서 만들어졌습니다.

현재 self.head가 None이 아님으로, else문으로 가야 합니다. 저희는 앞서 말했듯이 마지막 노드 다음에 new_node를 추가해줘야 합니다.

그렇기에 head 부터 시작하는 ptr 노드를 마지막 노드가 될 때까지 업데이트 해줘야 합니다.

ptr이 마지막 노드가 되면, ptr의 다음을 new_node로 연결해주면 됩니다.

이제 저희는 fourth 노드를 만들어줘야 합니다.

linkedlist.append(4)
Python
복사

fourth에 해당하는 new_node가 Node class에 의해서 만들어졌습니다.

현재 self.head가 None이 아님으로, else문으로 가야 합니다. 저희는 앞서 말했듯이 마지막 노드 다음에 new_node를 추가해줘야 합니다.

그렇기에 head 부터 시작하는 ptr 노드를 마지막 노드가 될 때까지 업데이트 해줘야 합니다.

ptr이 마지막 노드가 되면, ptr의 다음을 new_node로 연결해주면 됩니다.

이렇게 하여 저희는 목표한 linked list를 완성하였습니다. 그런데 한 가지 불편함이 있었습니다. ptr의 시작을 항상 처음 노드(head)에서 시작하여, 마지막 노드로 보내는 과정을 거쳐야 했습니다.

처음부터 마지막 노드를 알 수 있으면, 코드를 더욱 쉽게 구현 할 수 있을 것 같습니다. 따라서 마지막 노드를 가리키는 tail변수를 추가해보도록 합시다.

class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None
Python
복사

그렇게 되면 append 함수도 약간의 수정이 필요합니다. 새로운 원소가 추가 될 때마다, 마지막 노드인 tail을 업데이트 해줘야 하기 때문입니다.

전체 linked list 코드는 다음과 같습니다.

class Node(object):
    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
Python
복사

doubly linked list로의 확장

저희가 지금까진 배운 linked list는 한 쪽 방향으로만 갈 수 있기에 singly linked list라고 합니다. 이와 같은 linked list는 뒤로 갈 수 없기에 불편함을 가지고 있습니다. 어떻게 하면 뒤로 갈 수 있을까요?

그것은 Node에 이전 노드의 주소를 저장하면 됩니다.

class Node(object):
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None
Python
복사

append의 코드 또한 그렇게 많이 바뀌지 않습니다. 단순히 노드가 추가 될 때, tail의 노드를 가리키기만 하면 되는 것입니다.

class Node(object):
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
Python
복사

시간복잡도

Array의 경우 중간에 데이터를 삽입/삭제하게 되면 해당 index의 뒤에 있는 모든 원소들은 한 칸씩 shift를 해야만 하기 때문에

O(n)

의 시간복잡도를 갖게 되었습니다. 하지만 Linked list를 물리적으로 옮길 필요없이 next address가 가리키는 주소값만 변경하면 되기 때문에

O(1)

의 시간복잡도로 삽입/삭제가 가능합니다.

	Linked list	Array
access/update	$O(n)$	$O(1)$
insert_front	$O(1)$	$O(n)$
insert_at	$O(n)$	$O(n)$
insert_back	$O(n)$ \| $O(1)$	$O(1)$ amortized
remove_front	$O(1)$	$O(n)$
remove_at	$O(n)$	$O(n)$
remove_back	$O(n)$ \| $O(1)$	$O(1)$

insert_back과 remove_back의 경우 doubly linked list로 구현되어있으면

O(1)

의 시간복잡도를 가집니다.