[D-2] 자료구조의 이해 (연결리스트, 스택&큐) -2-

---

연결리스트(Linked List)

 

Linked List는 쉽게 말하면 데이터를 일렬로 연결한 데이터구조입니다. 각각의 데이터를 Node라고 부르고 각 노드는 데이터와 다음을 가르키는 포인터로 구성됩니다.

사실 무슨말인지 감이 안오시죠?

예를들어 저희가 사과와 바나나 그리고 오렌지를 가지고 있다고 가정해봅시다. 

이제 상자(Node)안에 사과를 넣고 바나나가 들어있는 상자의 위치를 알려주는 쪽지(Pointer)를 넣어줍시다.

다음으로는  바나나를 넣고 오렌지의 위치를 알려주는 쪽지를 넣어줍니다. 

그럼 저희는 오렌지를 찾기위해서 사과박스를 찾아보고 다음으로는 바나나가 든 박스를 찾아보고 최종적으로 오렌지의 위치를 알 수 있습니다.

이런 개념을 적용시킨 데이터구조가 연결리스트입니다!

간단하게 코드를 작성해볼까요?

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

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

    def add_node(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            last = self.head
            while last.next is not None:
                last = last.next
            last.next = new_node

    def remove_node(self, data):
        if self.head is None:
            return

        if self.head.data == data:
            self.head = self.head.next
            return

        curr = self.head
        while curr.next is not None:
            if curr.next.data == data:
                curr.next = curr.next.next
                return
            curr = curr.next

    def print_list(self):
        curr = self.head
        while curr is not None:
            print(curr.data)
            curr = curr.next

위 코드에서, add_node() 메소드는 데이터를 받아서 새로운 노드를 생성하고, 연결리스트의 끝에 추가합니다. remove_node() 메소드는 데이터를 받아서 해당 데이터를 가진 노드를 찾아서 삭제합니다. print_list() 메소드는 연결리스트를 처음부터 끝까지 순서대로 출력합니다.

다음으로는 실행을 해봅시다!

llist = LinkedList()

llist.add_node(1)
llist.add_node(2)
llist.add_node(3)
llist.add_node(4)

llist.remove_node(3)

llist.print_list()

다음과 같이 코드를 작성하면 최종적으로 LikedList안에는 1,2,3,4 노드를 추가하고 3번 노드를 삭제해 최종적으로

1,2,3 이 출력됩니다.

여기까지 이해하셨다면 연결리스트의 단점을 확실하게 알 수 있습니다. 특정노드를 찾으려면 처음부터 탐색해야하는 단점이 존재합니다.

반면 장점으로는 추가와 삭제가 굉장히 편리하다는 장점이 있습니다! 

---

스택(Stack)

여러분은 후입선출의 개념을 아시나요?

프로그래밍 관점에서 스택을 배울 때 많이 듣게 되는 말 중 하나가 Last In First Out 의 개념입니다.

말그대로 데이터를 넣을때 차곡차곡 쌓아두고 데이터를 뺄때 가장 최근에 쌓인 데이터부터 삭제하는 로직이죠.

예를들어서 여러분이 창고에서 택배를 쌓는일을 한다고 가정합시다. 여러분들은 이제 차곡차곡 택배를 쌓아야겠죠?그럼 이제 아래서 부터 택배가 쌓이게될겁니다. 그럼 반대로 이번엔 택배를 발송하기 위해서 가장 처음으로 쌓은 택배를 꺼내려면 당연히 위에서 부터 다시 쌓은 택배를 빼야할겁니다.

이러한 메커니즘을 가지고 동작하는 데이터구조가 바로 스택입니다.주로 컴퓨터적 관점에서는 임시로 데이터를 저장할때 사용합니다.

 

---

큐(Queue)

Stack과 비슷한 개념으로는 Queue가 있습니다. 다만 선입선출( Frist In Frist Out )의 개념을 적용한 데이터 구조입니다.

어려울건 없습니다! 데이터가 쌓이고 (Push) 데이터를 뺄때(Pop) 가장 처음으로 넣었던 데이터부터 빠지게 됩니다.

쉽게 설명하자면 저희가 만약 음식점에 줄을 서게된다면, 줄을 선 순서대로 주문을 하게되겠죠? 이러한 개념이 큐(Queue)라고 볼 수 있습니다.

주로 대기열을 관리할 때 많이 사용되는 방식입니다. 저희가 인터넷에서 어떤 파일을 다운로드할때 여러 파일을 받는다면, 하나의 파일이 전부 다운로드가 완료되고 다음 다운로드가 시작되는 방식이죠? 

이러한 경우도 큐의 개념을 적용시켰다고 볼수 있습니다.

---

 

자료구조는 헷갈릴때마다 한번 씩 틈틈히 봐줘야 좋은 것 같네요.