[알고리즘 공부] 2. 배열, 동적 배열, 단일 연결 리스트

배열의 삽입, 삭제, 탐색에 드는 시간 복잡도

삽입 : 최악의 경우, 가장 앞에 삽입 시 O(N)
(새로운 값 들어오면 다른 값들이 하나씩 자리 옮겨야 함. 단 맨 끝에 새로운 값 삽입하는 경우는 O(1))

삭제: 최악의 경우, 가장 앞에 걸 삭제 시 O(N)
(다른 값들이 하나씩 자리 옮겨야 함. 단 맨 끝에 삭제하는 경우는 O(1))

탐색: 최악의 경우, 찾는 값이 맨 끝에 있을 시 O(N)
(처음부터 끝까지 탐색, 그러나 인덱스로 찾을 시 k번째 원소를 찾으려면 (k-1)인덱스를 참조하면 돼서 O(1) 걸림.)

---

파이썬 배열 메서드의 시간 복잡도

arr.find(x) = 처음부터 끝까지 탐색함.최악의 경우 O(n)
arr.remove(x) =  삭제 후 이동. 최악의 경우 O(n)

---

동적 배열

정적 배열 : arr=[100] 이런 식으로 한 번 배열을 선언하면 메모리 공간 크기를 바꿀 수 없음.
동적 배열: 자유롭게 크기를 줄이고, 늘릴 수 있음. 사용할 만큼의 공간만 차지하게 해 메모리 낭비를 줄임.

동적 배열은 메모리를 필요할 때마다 사용할 수 있다. 
그 이유는 정적 배열은 index 기반으로 관리되지만, 동적 배열은 Index 기반이 아니기 때문이다. 그래서 메모리가 필요할 때마다 남은 공간에 추가적으로 할당하는 것이 가능하다.

하지만 정적배열과 같은 양의 데이터를 저장함에도 더 많은 메모리를 사용해서(여유분을 비축하기 때문에) 항상 동적 배열을 사용하는 것이 효과적이라 말할 수는 없다.

또한 동적 배열의 삽입, 삭제, 탐색 역시 정적 배열과 시간 복잡도는 같아서 이 또한 단점 중 하나이다.

---

연결 리스트(Linked List)

연결 리스트는 탐색은 느리나, 삽입과 삭제 연산을 O(1) 내에 빠르게 할 수 있어 삽입과 삭제가 잦은 상황에서 사용하는 자료 구조.

정보가 담긴 단위인 노드(node) 들이 연결된 자료구조.
노드는 데이터(data)와 다른 노드에 대한 참조(next)가 포함되어 있다. 

1) 단일 연결리스트(Singly Linked List)

이미지 추가--

• 연결 방향이 단방향인 연결리스트.
• 시작점의 노드를 Head, 도착점의 노드를 Tail이라 한다.
• 시간 복잡도
  - 탐색: Head부터 Tail까지 일일히 확인해야 하므로 최대 O(N)이 소요된다.
  - 삽입, 삭제: Next에 연결을 끊은 후, 다시 연결해주는 작업만 하면 되기 때문에 O(1) 이 소요된다.
  단, 일방향으로만 진행되기 때문에 뒤로 돌아갈 수 없는 구조임에 주의해야 한다.

* 예제 코드(Python) 

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


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

    # 출력
    def listprint(self):
        printval = self.head
        while printval != None:
            print(printval.data)
            printval = printval.next

    # head 앞에 삽입 : O(1)
    def insertHead(self, newdata):
        NewNode = Node(newdata)
        # 먼저 새 노드의 next를 현재 리스트의 head로 지정
        NewNode.next = self.head
        # 그 다음 현재 리스트의 head를 새 노드로 연결
        self.head = NewNode


    # tail 뒤에 삽입 : O(1)
    def insertTail(self, newdata):
        NewNode = Node(newdata)
        # 먼저 현재 리스트 tail의 next를 새 노드로 연결
        self.tail.next = NewNode
        # 현재 리스트의 tail을 NewNode로 지정
        self.tail = NewNode

    # 노드 사이에 삽입(특정 데이터를 가진 노드 뒤에 위치하도록) : O(1)
    def insertBetween(self, middle_node, newdata):
        if middle_node is None:
            print("The mentioned node is absent")
            return
        NewNode = Node(newdata)
        NewNode.next = middle_node.next
        middle_node.next = NewNode

    #삭제: O(1)
    def remove(self, removeKey):
        Headval = self.head

        if (Headval is not None):
            if (Headval.data == removeKey):
                self.head = Headval.next
                Headval = None
                return
            else:
                while (Headval is not None):
                    if Headval.data == removeKey:
                        break
                    prev = Headval
                    Headval = Headval.next

            if (Headval == None):
                return

            prev.next = Headval.next
            Headval = None

        else:
            return


    #탐색: 최악 O(N)
    def find(self, findData):
        Headval = self.head
        if (Headval is not None):
            if (Headval.data == findData):
                print('{} is in list!'.format(findData))
                return
            else:
                while(Headval is not None):
                    if Headval.data == findData :
                        print('{} is in list!'.format(findData))
                        return
                    prev = Headval
                    Headval = Headval.next

                print('{} is Not in List'.format(findData))

        else:
            print('{} is Not in List'.format(findData))

Slist = SLinkedList()
Slist.head = Node('Mon')
node2 = Node('Tue')
node3 = Node('Wed')
Slist.tail = node3

# 노드들을 연결해서 단일 링크드 리스트로 만들기
Slist.head.next = node2
node2.next = Slist.tail

# 노드에 삽입
Slist.insertHead('Sun')
Slist.insertTail('Fri')
Slist.insertBetween(Slist.head.next.next.next, 'Thu')
Slist.listprint()
print('---')

# 탐색(값 존재 O)
Slist.find('Thu')
print('---')

# 삭제
Slist.remove('Thu')
Slist.listprint()
print('---')

# 탐색(값 존재 X)
Slist.find('Thu')
print('---')

# 출력
Sun
Mon
Tue
Wed
Thu
Fri
---
Thu is in list!
---
Sun
Mon
Tue
Wed
Fri
---
Thu is Not in List
---

코드를 보며 느낀 건, 
1) 단일 리스트는 next만 존재하는 일방향 연결이라 이전의 node를 참고하기 힘들다는 점.
2) 맨 앞이나 뒤에 놓을 때처럼 들어갈 위치를 안다면 삽입, 삭제가 O(1)로 간단히 이뤄지긴 하지만, 위치를 모르고 특정 데이터 뒤에 두고 싶다면, 안의 데이터를 탐색하는 과정이 들어갈 수밖에 없기 때문에 탐색 과정이 필요하다.

코드 짤 때 이 사이트 참고했다. 파이썬으로 자료구조.알고리즘 예시코드 살펴보기 유용한 사이트인듯!

Python - Linked Lists

---

참고: 코드트리(https://www.codetree.ai/)

코드트리