[ 자료구조 ] 배열, 스택, 큐, 링크드리스트, 해쉬

자료구조~ 자료구조~ 하는데 자료구조가 뭔지 알아보자.

정의

자료구조는 컴퓨터에서 처리할 자료를 효율적으로 관리하고 구조화시키기 위한 학문이다.

나는 마트를 생각했다.
마트에 존재하는 많은 상품들을 자료(Data)라고 생각하고, 이 상품들이 진열되어 있는 방식을 구조화라고 생각한다. 이 진열되어 있는 방식에 따라 마트 관리자가 상품을 꺼내고, 빼고 하는 행위들이 더욱 효율적이게 만든다.

종류

배열 ( Array ), 스택 ( Stack ), 큐 ( Queue ), 링크드 리스트 ( Linked List ), 해쉬 ( Hash ) 등 여러가지의 종류가 있으며, Python에서 list,set,dict,tuple 등으로 구현할 수 있다.

배열 ?

배열은 데이터들을 하나의 변수에 담아 관리할 수 있는 자료구조다.
배열은 순서를 가지고 있기 때문에 인덱스를 통한 접근이나, loop문을 통해 처리할 수 있다.

출처 : 네이버 지식백과

간단해 보이는데 배열말고 여러가지 자료구조가 있는것을 보면 장점과 단점이 존재한다는 의미이다.

• 장점
  • 배열에 있는 데이터에 접근할 때 index를 통해 빠르게 접근이 가능하다.
    

• 단점
  • 배열은 데이터를 삭제할 경우 메모리의 빈 공간이 생기고, 추가할 경우 배열의 메모리 공간이 많이 필요하다. 즉, 데이터의 추가와 삭제가 효율적이지 못하다는 단점이 있다.

Python 구현

스택 ?

스택(Stack)은 데이터의 추가와 삭제가 한쪽 방향에서만 일어나는 구조이다.
보통 후입선출(LIFO - Last In First Out )이라는 용어를 사용한다.

출처: 네이버 지식백과

위와 같이 아래가 막힌 동전케이스가 있을 때, 맨 마지막으로 들어온 동전이 가장 먼저 케이스에서 나오는 구조를 말한다.

• 장점

  • 구조가 단순하여 구현이 쉽고, 데이터 접근이 빠르다.
    

• 단점

  • 보통 배열구조를 활용하여 구현하기 때문에 메모리 문제가 발생한다.

Python 구현

큐 ?

큐(Queue)는 스택과 다르게 데이터를 추가하는 방향과 삭제하는 방향이 다른 구조이다.
보통 선입선출 ( FIFO - First In First Out )이라는 용어를 사용한다.

출처: 네이버 지식백과

위와 같이 계산대에 먼저 들어온 사람(Data)이 먼저 나가는 구조이다.

• 장점
  • 데이터의 삽입과 삭제가 빠르다.
    
    
• 단점
  • 데이터를 삭제할 때 그 공간이 쓸모 없는 공간이 되어 문제가 발생한다. ( 순환구조로 해결하려고 함 )

Python 구현

링크드 리스트 ?

링크드 리스트(Linked List)는 배열구조와는 다르게 element끼리 연결하여 이용하는 구조이다.
배열구조의 경우 각 데이터들을 element라고 칭하지만, 링크드 리스트에서는 node라고 칭한다.
node에는 현재의 데이터와 연결되어 있는 다음 node의 주소가 포함되어 있다.

출처: 네이버 지식백과

• 장점
  • 데이터의 삽입과 삭제가 쉽다.
  • 링크드 리스트의 길이를 동적으로 조절할 수 있다.
    
    
• 단점
  • 원하는 데이터에 바로 접근할 수 없다.
  • 현재 데이터와 다음 노드의 정보를 담기 위한 추가 공간이 필요하다.

Python 구현

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

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


    def append(self,node):

        if self.head:
            cur_node = self.head
            while cur_node.next:
                cur_node = cur_node.next

            cur_node.next = node

        else:
            self.head = node

    def InsertNode(self,node,index):

        cur_node = self.head
        pre_node = None
        cur_idx = 0

        if index == 0:
            if self.head:
                next_node = self.head
                self.head = node
                self.head.next = next_node

            else:
                self.head = node

        else:

            while cur_idx < index:
                if cur_node:
                    pre_node = cur_node
                    cur_node = cur_node.next

                else:
                    break

                cur_idx += 1
            if cur_idx == index:
                node.next = cur_node
                pre_node.next = node

            else:
                return -1

    def DeleteIndex(self,index):

        cur_index = 0
        cur_node = self.head
        pre_node = None
        next_node = self.head.next

        if index == 0:
            self.head = next_node

        else:
            while cur_index < index:
                if cur_node.next:
                    pre_node = cur_node
                    cur_node = next_node
                    next_node = next_node.next

                else:
                    break
                cur_index += 1

            if cur_index == index:
                pre_node.next = next_node

            else:
                return -1

    def Prt(self):
        cur_node = self.head

        out = ""
        while cur_node:
            out += str(cur_node.data)

            cur_node = cur_node.next

        return out


if __name__ == "__main__":

    LL = SinglyLinkedList()
    LL.append(Node(1))
    print(LL.Prt())
    LL.append(Node(2))
    print(LL.Prt())
    LL.append(Node(3))
    print(LL.Prt())
    LL.append(Node(4))
    print(LL.Prt())

    LL.InsertNode(Node(5),2)
    print(LL.Prt())

    LL.DeleteIndex(2)
    print(LL.Prt())

• 단일 연결 구조를 기준으로 이중 연결 구조, 순환 연결 구조가 있다. 단일 연결의 구조를 잘 알아두면 나머지 구조는 쉽게 이해할 수 있다.
  
  
  

  • 이중 연결 구조 ( Doubly linked list )
    

    출처 : 위키디피아

    단일 연결 구조는 next 노드에 대한 정보를 담고 있지만, 이중 연결 구조는 이전 노드에 대한 정보도 가지고 있다. 즉, 2개의 포인터 공간이 존재한다.
    
    이러한 구조가 나온 이유는 단일 연결 구조에서는 할 수 없던 역으로 출력하는 것이 가능하다.
    하지만 포인터 공간이 늘어난 만큼 메모리 낭비가 일어난다.

    
    
    

  • 순환 연결 구조 (circular linked list)

    

    출처 : 위키디피아

    순환 또는 환형 연결 리스트는 포인터가 1개냐, 2개냐가 초점이 아니라 모든 노드의 Next가 이어져 None의 값이 존재하지 않는 구조이다.

    
    
    

해쉬 ?

해쉬테이블(Hash table)이란 key : value가 한 쌍으로 존재하며, key값이 일련의 함수를 통해 저장하는 배열의 인덱스로 사용되기 때문에 데이터 접근과 삽입과 같은 행위에서 효율적이다.

해쉬함수 ( Hash Function )란 key값들을 인덱스로 사용하기 위해 정수(해쉬)로 변환시켜주는 함수를 의미한다. 상황마다 적절하게 어떤 함수를 써야할지는 개발자의 선택이다.

출력

파이썬의 기본 함수 hash()와 hashlib을 사용해 암호학적인 해쉬함수를 사용할 수 있다.

파이썬의 자료구조인 딕셔너리는 해쉬 테이블로 구현되어 있다.