[내일배움캠프 11일차 TIL] 자료구조 - 연결리스트(Linked list)/스택(Stack)

내가 너무 어려워했던 알고리즘과 자료구조....

코드 자체를 이해하기 어려워서 거의 놓아버렸지만

이걸 놓으면 코테를 할 수가 없다는 사실,,,,,,

절망적이지만 어쩌겠어... 해야지......

---

자료 구조에는 여러 종류가 있지만, 오늘 알아볼 자료구조는 연결리스트와 스택이다.

 

연결리스트?

연결리스트는 데이터의 구조를 순서대로 저장하는 자료구조로

각 요소는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다

 

연결리스트는 스택(stack), 큐(queue), 그래프(graph) 등의 자료구조를 구현할 때 많이 사용한다.

 

 

연결리스트는 위와 같은 형태를 가진다고 볼 수 있다

그래서 만약 데이터의 삽입이 필요한 상황이 생기면

 

 

이렇게 포인터를 바꾸어주어서 데이터를 삽입하거나 삭제하기에 용이하다는 것이다

 

 

 

연결리스트의 장/단점

• 장점: 데이터의 삽입과 삭제가 쉽고 빠르다. 특히 중간에 요소를 삽입하거나 삭제할 때 유리함.
• 단점: 특정 위치의 요소에 직접 접근할 수 없어 임의 접근이 불가능하며, 메모리 공간을 많이 사용할 수 있다(포인터 때문)

 

 

구현

챗 지피티에게 파이썬으로 연결리스트를 구현해달라고 요청했다

# 연결리스트의 노드 클래스 정의
class Node:
    def __init__(self, data=None):
        self.data = data  # 노드가 저장하는 데이터
        self.next = None  # 다음 노드를 가리키는 포인터

# 연결리스트 클래스 정의
class LinkedList:
    def __init__(self):
        self.head = None  # 연결리스트의 첫 번째 노드를 가리키는 헤드 포인터

    # 연결리스트 끝에 새로운 노드 추가하기
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    # 연결리스트 출력하기
    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 연결리스트 테스트
if __name__ == '__main__':
    # 새로운 연결리스트 생성
    linked_list = LinkedList()

    # 데이터 추가
    linked_list.append(1)
    linked_list.append(2)
    linked_list.append(3)
    linked_list.append(4)

    # 연결리스트 출력
    linked_list.print_list()

 

 

 

코드를 실행하면 다음과 같은 결과를 얻을 수 있다

 

 

 

 

 

 

---

스택?

스택은 LIFO(Last In, First Out)의 원칙을 따르는 자료구조이다. 즉 가장 마지막에 추가된 요소가 가장 먼저 제거가 된다

스택은 자료를 임시로 저장하거나 역순으로 출력해야 하는 상황에서 유용하게 사용된다. 그리고 후입선출의 특징을 가지기 때문에 깊이 우선 탐색(DFS, Depth-First Search) 등의 알고리즘에 사용된다

 

 

 

스택은 주로 다음과 같은 기본 연산을 가진다

• Push: 스택의 맨 위(가장 최근)에 요소를 추가
• Pop: 스택의 맨 위(가장 최근)에 있는 요소를 제거하고 반환
• Peek 또는 Top: 스택의 맨 위에 있는 요소를 반환하지만 제거하지는 않음
• isEmpty: 스택이 비어있는지 확인

 

구현

스택 역시 챗지피티에게 파이썬으로 구현해달라고 요청했다

# 스택 클래스 정의
class Stack:
    def __init__(self):
        self.items = []  # 스택으로 사용할 리스트

    # 스택에 요소 추가 (Push)
    def push(self, item):
        self.items.append(item)

    # 스택에서 요소 제거 및 반환 (Pop)
    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    # 스택의 맨 위 요소 반환 (Peek)
    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    # 스택이 비어있는지 여부 확인
    def is_empty(self):
        return len(self.items) == 0

    # 스택의 크기 반환
    def size(self):
        return len(self.items)

# 스택 테스트
if __name__ == '__main__':
    # 새로운 스택 생성
    stack = Stack()

    # 데이터 추가 (Push)
    stack.push(1)
    stack.push(2)
    stack.push(3)

    # 스택 출력
    print("Current stack:", stack.items)

    # 데이터 제거 및 반환 (Pop)
    popped_item = stack.pop()
    print("Popped item:", popped_item)
    print("Current stack:", stack.items)

    # 맨 위 요소 확인 (Peek)
    top_item = stack.peek()
    print("Top item:", top_item)

    # 스택이 비어있는지 확인
    print("Is stack empty?", stack.is_empty())

    # 스택의 크기 확인
    print("Stack size:", stack.size())

 

 

 

위의 코드를 실행한 결과는 다음과 같다

 

 

파이썬은 리스트라는 자료형을 사용하기 때문에 연결리스트를 사용하지 않아도 스택을 구현할 수 있다

그러면 연결리스트를 사용한 스택은 어떻게 구현이 되는가?

이것 또한 챗지피티에게 연결리스트를 사용해서 스택을 구현해달라고 요청했다

 

 

# 연결리스트의 노드 클래스 정의
class Node:
    def __init__(self, data=None):
        self.data = data  # 노드가 저장하는 데이터
        self.next = None  # 다음 노드를 가리키는 포인터

# 연결리스트 기반 스택 클래스 정의
class Stack:
    def __init__(self):
        self.top = None  # 스택의 맨 위(최상단)을 가리키는 포인터

    # 스택에 요소 추가 (Push)
    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    # 스택에서 요소 제거 및 반환 (Pop)
    def pop(self):
        if self.is_empty():
            return None
        popped_data = self.top.data
        self.top = self.top.next
        return popped_data

    # 스택의 맨 위 요소 반환 (Peek)
    def peek(self):
        if self.is_empty():
            return None
        return self.top.data

    # 스택이 비어있는지 여부 확인
    def is_empty(self):
        return self.top is None

# 스택 테스트
if __name__ == '__main__':
    # 새로운 스택 생성
    stack = Stack()

    # 데이터 추가 (Push)
    stack.push(1)
    stack.push(2)
    stack.push(3)

    # 스택 출력
    print("Current stack:")
    current_node = stack.top
    while current_node:
        print(current_node.data)
        current_node = current_node.next

    # 데이터 제거 및 반환 (Pop)
    popped_item = stack.pop()
    print("Popped item:", popped_item)

    # 맨 위 요소 확인 (Peek)
    top_item = stack.peek()
    print("Top item:", top_item)

    # 스택이 비어있는지 확인
    print("Is stack empty?", stack.is_empty())

 

위 코드를 실행한 결과는 다음과 같다

 

 

 

 

 

 

 

내가 이해한 스택을 그림으로 표현해보자면

 

 

 

 

 

 

이런 느낌이려나,,,

 

 

 

 

---

 

이때까지 연결리스트랑 스택이 별개의 자료구조인 줄 알았다....

어려운 자료구조의 세계....

어떤 느낌인지는 알겠는데 막상 사용하려니 어렵달까....

알 것 같으면서 모르겠다...ㅎㅎ

 

 

알고리즘주차 들어가기 전 부터 꽤나 걱정스럽지만 열심히 복습하고 반복해야지...