배열, 리스트, 연결리스트

배열

배열이란

배열은 메모리 덩어리이다. 메모리 공간을 반드시 연속적으로 차지해, 인덱스를 통해 접근할 수 있는 자료구조를 의미한다. 하나의 변수에 여러 자료를 저장할 수 있고, 반복문을 통해 효과적으로 데이터 처리가 가능하다.

배열의 특징

• 크기(Element의 개수)가 정해져 있다.
• 자료 구조에 기능(메소드)이 포함되어 있지 않다.
• 자료가 메모리상에 빈틈 없이 연속적으로 위치해 있다.
• 인덱스를 활용하여 자료에 빠르게 접근할 수 있다.

메소드가 포함되어 있지 않다는 것은 많은 것을 의미한다. 색인, 덮어쓰기 즉 메모리에 접근해서 데이터를 다루는 것 외에는 특정한 기능을 제공하지 않는다. 때문에 특정 인덱스 삭제, 특정 인덱스에 접근해서 삽입하고 밀어내기 등의 기능을 제공하지 않는다.

배열의 단점

• 배열의 길이는 생성 시 정해져, 변경할 수 없다.
  • 가변 길이 배열은 배열의 크기를 변경할 때 마다 새 배열을 만든다.
• Element를 제거할 경우, 배열에 빈 틈이 생긴다.
  • 기존 Element의 인덱스를 유지하기 위해 빈 틈을 유지한다.
  • 실제로는 Element의 삭제가 불가능하다.

일반적으로 배열이 삭제를 할 경우 O(n) 의 시간이 걸리고 삽입할 때 O(n)의 시간이 걸린다고 하는 것은 리스트 추상데이터의 특징이다.

배열은 삽입이 불가능하고, 삭제를 할 경우 따로 인덱스 이동없이 그 칸을 비워둔다.

리스트

리스트는 추상 데이터 타입이다. 이 리스트 추상데이터타입을 배열이나 연결리스트를 통해 구현하게 되고, 이렇게 만들어지는 자료구조가 arrayList, 파이썬의 리스트가 되는 것이다.

리스트의 연산자

1. constructor(생성자) : 맨 처음 자료구조를 선언하는 메소드
2. is_empty : 비었나 확인 하는 메소드
3. append : 뒤에 붙이기
4. prepend : 앞에 붙이기
5. access : 접근
6. insert : 삽입
7. remove : 삭제

배열리스트로 구현

class ArrayList:
    def __init__(self, capacity):
        self.capacity = capacity # 전체 용량
        self.length = 0  # 현재 차지하고 있는 용량
        self.array = array.array('l', [0] * capacity)

    def is_empty(self):
        if self.length == 0:
            return True
        else:
            return False

    def check_capacity(self): # 현재 용량이 전체 용량을 초과하는지 확인하는 함수
        if self.length + 1 > self.capacity:
            self.capacity *= 2
            temp_array = array.array('l', [0] * self.capacity)
            for i in range(self.length):
                temp_array[i] = self.array[i]
            self.array = temp_array


    def prepend(self, value):
        # capacity 확인 후 추가했을 때 length 가 capacity를 초과하지 않을 경우 추가
        self.check_capacity()
        if self.length == 0:
            self.array[0] = value

        else:
            for i in range(self.length, 0, -1):
                self.array[i] = self.array[i - 1]
            self.array[0] = value
        self.length += 1

    def append(self, value):
        self.check_capacity()
        self.array[self.length] = value
        self.length += 1

    def set_head(self, index):
        self.length -= index
        temp_array = array.array('l', [0] * self.capacity)
        for j in range(self.length): # 잘못된 구현 -> 수정 필요 index만 옮기도록
            temp_array[j] = self.array[index+j]
        self.array = temp_array

    def access(self, index):
        if index >= self.length or index < 0:
            return "index out of range."
        return self.array[index]


    def insert(self, index, value):
        if index >= self.length or index < 0:
            return "index out of range."

        self.check_capacity()
        for i in range(self.length, index, -1):
            self.array[i] = self.array[i-1]
        self.array[index] = value
        self.length += 1


    def remove(self, index):
        if index >= self.length or index < 0:
            return "index out of range."
        for i in range(index, self.length):
            self.array[i] = self.array[i+1]
        self.length -= 1


    def print(self):
        for i in range(self.length):
            print(self.array[i], end=" ")
        print()

is_empty(): O(1) - 조건문 1회 실행으로 종료

prepend(): O(n) - for문 1회 실행

append(): O(n) (조건부 O(1)) - 용량 초과 시 새로운 배열로 이동시켜주어야 하므로 O(n)이지만 용량 확보가 되어있다면 O(1)

set_head(index): O(1) - 인덱스만 바꿔주면 되므로 O(1)

access(index): O(1) - 인덱스로 접근하면 O(1)
insert(item, index): O(n) - 삽입할 경우 기존 뒤에 있던 원소를 하나씩 모두 옮겨서 공간 확보를 해준다음 삽입해야 하므로 O(n)
remove(index): O(n) - 삭제할 경우 삭제한 원소 자리의 뒤의 모든 원소를 땡겨서 자리를 채워주어야 하므로 O(n)

연결리스트로 구현

연결리스트는 메모리 상의 연속성을 보장하지 않는 데이터 구조이다. 하지만 다음 데이터를 참조할 수 있는 변수를 따로 저장해주는 것을 통해 연속성을 구현한다.

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


class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.length = 0

    def is_empty(self):
        if self.head == None:
            return True
        else:
            return False

    def prepend(self, value):
        if self.head == None:
            node = Node(value, None)
        else:
            node = Node(value, self.head)
        self.head = node
        self.length += 1

    def append(self, value):
        if self.head == None:
            node = Node(value, None)
            self.head = node
        else:
            node = Node(value, None)
            curr = self.head
            while curr.next != None:
                curr = curr.next
            curr.next = node
        self.length += 1

    def set_head(self, index):
        if self.length <= index or index < 0:
            return "list index out of range"
        else:
            curr = self.head
            for _ in range(index):
                curr = curr.next
            self.head = curr
        self.length -= index


    def access(self, index):
        if self.length <= index or index < 0:
            return "list index out of range"
        else:
            curr = self.head
            for _ in range(index):
                curr = curr.next
            return curr.value

    def insert(self, index, value):
        if self.length <= index or index < 0:
            return "list index out of range"
        else:
            if index == 0:
                self.prepend(value)
            else:
                curr = self.head
                for _ in range(index - 1):
                    curr = curr.next
                node = Node(value, curr.next)
                curr.next = node

    def remove(self, index):
        if self.length <= index or index < 0:
            return "list index out of range"
        if index == 0:
            self.head = self.head.next

        else:
            curr = self.head
            for _ in range(index - 1):
                curr = curr.next
            curr.next = curr.next.next


    def print(self):
        curr = self.head
        while curr != None:
            print(curr.value, end=" ")
            curr = curr.next
        print()

is_empty(): O(1) - 헤드 노드를 확인했을 때 None인지만 확인하면 되므로 O(1)
prepend(): O(1) - 삽입 후 head 노드의 참조 변수만 바꿔주면 되므로 O(1)
append(): O(n) - head 부터 마지막 노드가 어디인지 모두 순회 후 추가해야 하므로 O(n)
set_head(index): O(n) - index의 노드 위치를 확인해야 하므로 head 부터 O(n) 으로 순회
access(index): O(n)- index의 노드 위치를 확인해야 하므로 head 부터 O(n) 으로 순회
insert(item, index): O(1) (w/o access) - 삽입 자체는 참조변수만 변경해주면 되므로 O(1) 이지만 이 index 를 찾는데 O(n) 이 소모됨
remove(index): O(1) (w/o access) - 삭제도 똑같음.

big O notation으로만 따지면 연결리스트와 배열리스트의 성능에 큰 차이가 없어 보이지만 사실 연결리스트가 훨씬 연산량이 적다. 왜냐하면 연결리스트의 연산은 대부분 색인에서 발생하기 때문에, 비교 연산만 진행하면 되지만, 배열의 경우에는 인덱스에 있는 값을 모두 옮겨주는 연산이기 때문에, 비교, 삽입 등의 연산이 더 많이 발생하게 된다.