자료구조(Data Structure)란?
자료구조의 정의
- 전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법입니다.
- 데이터 특성에 따라서, 체계적인 데이터 구조화가 필요하며, 이러한 데이터 구조는 코드의 효율성과 성능을 결정합니다.
자료구조의 종류
- 대표적인 자료구조로는 배열(Array), 큐(Queue), 스택(Stack), 링크드 리스트(Linked List), 해쉬 테이블(Hash Table), 힙 (Heap) 등이 존재합니다.
- Python에서는 대표적으로 List, Tuple, Set, Dictionary가 존재하며, 위의 자료구조 대부분을 모두 구현할 수 있습니다.
1. 배열(Array)
- 장점 : Array는 논리적 순서와 물리적 순서가 일치합니다. 따라서 index값을 통한 원소 접근이 용이하여 빠른 접근이 가능하며, 구현하기가 쉽습니다.
- 단점 : 삽입, 삭제 등에 대한 연산에 필요한 Cost가 높습니다. 삭제의 경우 순서를 맞추기 위해, 뒤의 원소들을 모두 앞으로 Shift 연산을 해줘야 하며, 삽입의 경우에도 삽입한 인덱스를 포함하여 뒤 인덱스들에 대해 Shift 연산을 필요로 합니다. 또한 데이터 추가 시 공간이 많이 필요하며, 삭제 시 공간이 생겨 이를 관리해주어야 합니다. 길이 조절이 어렵다는 단점이 있습니다.
arr = [1,2,3,4,5] # 1차원 배열
str = 'Hello World'
print(arr[2]) # 3
print(str[2]) # l
arr2 = [[1,2,3],[4,5,6],[7,8,9]] # 2차원 배열
print(arr2[1][2]) # 62. 링크드 리스트(Linked List)
- 배열의 삽입/삭제 연산에 대한 비효율성을 개선하고자 등장한 것이 Linked List입니다.
- Linked List는 논리적으로는 순서대로 되어있으나, 물리적으로는 순서대로 되어있지 않습니다.
- 장점 : 각 원소가 다음 index의 주소를 가지고 있어, 삽입/삭제시 데이터를 Shift할 필요 없이 해당되는 원소의 물리적 주소만 변경해주면 됩니다. 또한 미리 데이터 공간을 할당할 필요가 없습니다.
- 단점 : index를 참조하기 위해서는, 1번 index부터 차례대로 접근해야 합니다 (속도가 느립니다). 또한 연결을 위한 별도 데이터 공간이 필요하므로 효율이 낮으며, 중간 데이터를 삭제할 경우에는 앞 뒤를 모두 고려하여 코드를 재구성하여 작성해야 합니다.
기능
- Node : 데이터 저장 단위로, 데이터 값과 포인터로 구성되어 있습니다.
- Pointer : 각 노드 안에서, 다음이나 이전 노드의 주소를 가지는 값을 의미합니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def add(self, data):
new_node = Note(data)
if not self.head:
self.head = new_node
else:
node = self.head
while node.next:
node = node.next
node.next = new_node
def delete(self, data):
node = self.head
if node.data == data:
self.head = node.next
del node
else:
node = node.next
def find(self, data):
node = self.head
while node:
if node.data == data:
return node
else:
node = node.next
def print(self):
node = self.head
while node:
print(node.data)
node = node.next해쉬 테이블, 트리, 힙은 다음 포스팅에서 정리하도록 하겠습니다.
참조
댓글