자료구조 | 연결리스트(python 구현)

📒 자료형과 자료구조

• 자료형 : 어떤 자료가 식별될 수 있는 방법과 그 자료에 대한 여러가지 연산을 결정하는 것으로, 자료를 특정 분류에 따라 올바르게 표현하기 위한 정의와 그 구현을 의미한다.
  👉 추상적 자료형 : 자료들과 그 자료에 대한 연산들을 명시한 것(구현 방법을 명시하고 있지 않다.)
• 자료구조 : 자료를 저장하는 구조로, 추상적 자료형을 구체적으로 정의한 결과

추상적 자료형 예시

1) 추상적 자료형 : 리스트
2) 자료구조 : 배열, 연결리스트 등등...

🍑 연결리스트(Linked List)

추상적 자료형인 '리스트'를 구현한 자료구조, 노드와 포인터로 이루어져 있다.
👉 노드는 자료의 값, 포인터는 자신의 다음 순서 노드를 가리킨다

• 어떠한 데이터를 저장할 때 그 다음 순서의 자료가 있는 위치에 데이터를 포함시켜 자료를 저장한다. 이 때, 저장되는 데이터는 노드(node), 그 다음 데이터는 포인터(pointer)가 된다.
• 크게 단순 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List)로 나눌 수 있다.

🧩 장점

• 자료의 추가와 삭제가 편한다.
  👉 최악의 경우 O(n)의 시간 복잡도를 갖지만, 기본적으로는 O(1)이다.(들어갈 위치를 찾아서 선을 긋기만 하면 된다!)

🙈 단점

• 특정 위치의 자료를 찾는 것이 번거롭다.
• 자료의 위치가 시작점에서 멀수록 연산 횟수가 증가한다.

장단점 정리

'배열'과 비교해 보면 배열은 배열 내의 특정 순서의 값을 조회하고자 할 때 단번에 찾아낼 수 있지만 자료를 추가할 때는 조금 번거롭다는 단점이 있다. 즉, 새로운 자료가 추가되면서 자료들의 순서를 변경해 주어야 한다는 단점이 있는데 반해 연결리스트는 새로운 자료의 추가(또는 삭제)가 비교적 편하다는 장점이 있다.

🍓 연결리스트의 종류

• 단순 연결 리스트 : 가장 단순한 형태의 연결리스트로, 다음 노드에 대한 참조만을 가진다. 가장 마지막 원소를 찾기 위해서는 리스트 끝까지 찾아가야 한다는 단점이 있다. 보통 큐를 구현할 때 사용한다.
  👉 단순 연결 리스트는 Head 노드를 참조하는 주소를 잃어버리게 되면 전체 데이터를 못 쓰게 되는 단점이 있다.

• 이중 연결 리스트 : 다음 노드의 참조 뿐만 아니라 이전 노드의 참조도 같이 가리키는 연결 리스트이다.
  👉 단순 연결 리스트는 삽입 또는 삭제시 반드시 이전 노드를 가리키는 참조를 추가로 알아야 한다는 단점이 있지만 이중 연결 리스트는 현재 노드를 삭제하는 것이 훨씬 간단함

• 원형 연결 리스트 : 단순 연결 리스트에서 마지막 원소는 Null을 가리키는데, 만약 이 대신 '처음 노드'를 가리키게 한 것이 원형 연결 리스트이다.

🥝 연결 리스트 구현

[이중 연결 리스트 : python으로 구현]

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


class DoublyLinkedList:
    def __init__(self):
        self.head = Node(None, None, None)
        self.tail = Node(None, self.head, None)
        self.head.next = self.tail
        self.length = 0

    def size(self):
        return self.length

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

    # present가 가리키는 이전 노드 앞에 새로운 노드 삽입
    def insert_before(self, present, data):
        old = present.prev  # 이전 노드
        new_node = Node(data, old, present)
        # 현재 노드의 이전 노드에 새로운 노드 추가
        present.prev = new_node
        old.next = new_node

        self.length += 1

    # present가 가리키는 다음 노드 앞에 새로운 노드 삽입
    def insert_after(self, present, data):
        old = present.next
        new_node = Node(data, present, old)
        old.prev = new_node
        present.next = new_node

        self.length += 1

    # 노드 n 삭제
    def delete(self, n):
        if self.is_empty():
            return "빈 리스트입니다."

        front = n.prev  # 앞 노드
        rear = n.next  # 뒷 노드
        front.next = rear
        rear.prev = front

        self.length -= 1

        return n.data

    # 데이터 검색 : head부터
    def search_from_head(self, data):
        if self.head == None:
            return False

        node = self.head
        while node:
            # 데이터 일치할 경우 True 리턴
            if node.data == data:
                return True
            else:
                node = node.next

        return False

    # 데이터 검색 : tail부터
    def search_from_tail(self, data):
        if self.head == None:
            return False

        node = self.tail
        while node:
            if node.data == data:
                return True
            else:
                node = node.prev

        return False

    # 리스트 출력
    def get_list(self):
        result = []
        current = self.head

        while current != None:
            result.append(current.data)
            current = current.next

        return result

참조(References)

1)연결리스트의 종류

• https://namu.wiki/w/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8