자료구조의 구현

자료구조의 구현 기술

자료구조의 종류는 많지만 실제 자료구조를 구현하는 기술은 리스트(List)와 연결리스트(Linked List) 두 가지가 있다.

• 리스트(List) : 데이터들이 연속적인 공간을 할당받아 만들어지는 구조
• 연결 리스트(List) : 데이터들이 각각 공간을 할당받고, 데이터 사지의 연결 고리가 만들어지는 구조
  
  

리스트형 자료구조

연속적인 저장의 형태를 지닌다.

• 배열 : 크기가 변하지 않는 리스트형 자료구조. 중간 값을 삭제해도 빈칸으로 유지.
• 리스트 : 크기가 변하는 리스트형 자료구조. 중간 값을 삭제하면 뒤의 값이 앞으로 이동.
  
  

연결 리스트 자료구조

저장하는 각 데이터가 데이터 외에 다음과 이전의 데이터를 가리키는 정보를 가지고 있는 구조.

• 연결 리스트 : 저장된 각 데이터가 (데이터)+(다음 데이터의 포인터)로 이루어진 것. 한 방향으로만 탐색 가능.
• 더블 연결 리스트 : 저장된 각 데이터가 (이전 데이터의 포인터)+(데이터)+(다음 데이터의 포인터)로 이루어진 것. 양 방향 탐색 가능.
• 환형 연결 리스트 : 더블 연결 리스트의 양 끝이 연결되어 있는 구조.

삽입과 삭제를 할 때는 전체 데이터의 변동이 없고 앞, 뒤의 연관된 데이터만 변동이 있다.
따라서 중간에 삽입, 삭제는 빠르게 수행할 수 있지만 특정 데이터를 찾는 것은 포인터를 따라 이동해야 하므로 성능이 떨어진다.

python 3.8 
# Linked List

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

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

    def append(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node

    def delete(self, data):
        prev_node = self.head
        if self.head.value == data:
            self.head = self.head.next
            del prev_node
        else:
            next_node = self.head.next
            while next_node:
                if next_node.value == data:
                    prev_node.next = next_node.next
                    del next_node
                    break
                prev_node = next_node
                next_node = next_node.next

github : https://github.com/honeybeeveloper/data-structure/blob/develop/linked-list.py
참고 : 책 <그림으로 정리한 알고리즘과 자료구조>