파이썬 자료구조
배열
arr = [27, 36, 45]
단일 연결 리스트
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def insert_at_head(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert_at_position(self, data, position):
if position == 0:
self.insert_at_head(data)
return
new_node = Node(data)
current = self.head
for _ in range(position - 1):
if current is None:
return # position out of bounds
current = current.next
if current is None:
return
new_node.next = current.next
current.next = new_node
def delete(self, key):
current = self.head
prev = None
while current:
if current.data == key:
if prev:
prev.next = current.next
else:
self.head = current.next
return
prev = current
current = current.next
def search(self, key):
current = self.head
while current:
if current.data == key:
return True
current = current.next
return False
def traverse(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
이중 연결 리스트
노드가 앞/뒤 두 방향 모두로 연결되는 리스트이다.
head 뿐만이 아니라 tail도 있다.
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert_at_head(self, data):
new_node = Node(data)
if not self.head:
self.head = self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def insert_at_tail(self, data):
new_node = Node(data)
if not self.tail:
self.head = self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
원형 연결 리스트
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyCircularLinkedList:
def __init__(self):
self.head = None
self.current = None
def insert_at_head(self, data):
new_node = Node(data)
if not self.head:
new_node.next = new_node.prev = new_node
self.head = self.current = new_node
else:
tail = self.head.prev
new_node.next = self.head
new_node.prev = tail
tail.next = self.head.prev = new_node
self.head = new_node
def insert_at_tail(self, data):
new_node = Node(data)
if not self.head:
new_node.next = new_node.prev = new_node
self.head = self.current = new_node
else:
tail = self.head.prev
new_node.prev = tail
new_node.next = self.head
tail.next = self.head.prev = new_node
def delete_from_head(self):
if not self.head:
return
if self.head.next == self.head:
self.head = self.current = None
return
tail = self.head.prev
if self.current == self.head:
self.current = self.head.next
self.head = self.head.next
self.head.prev = tail
tail.next = self.head
def delete_from_tail(self):
if not self.head:
return
if self.head.next == self.head:
self.head = self.current = None
return
tail = self.head.prev
new_tail = tail.prev
if self.current == tail:
self.current = self.head
new_tail.next = self.head
self.head.prev = new_tail
def move_next(self):
if self.current:
self.current = self.current.next
def move_prev(self):
if self.current:
self.current = self.current.prev
def print_current(self):
if self.current:
print("Current:", self.current.data)
else:
print("Current: None")
def traverse_forward(self):
if not self.head:
print("Empty")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print("(head)")
def traverse_backward(self):
if not self.head:
print("Empty")
return
current = self.head.prev
while True:
print(current.data, end=" <- ")
current = current.prev
if current == self.head.prev:
break
print("(tail)")
스택
class ArrayStack:
def __init__(self, capacity):
self.stack = [None] * capacity
self.capacity = capacity
self.top = -1
def push(self, item):
if self.top + 1 == self.capacity:
raise Exception("Stack is full")
self.top += 1
self.stack[self.top] = item
def pop(self):
if self.is_empty():
raise Exception("Stack is empty")
item = self.stack[self.top]
self.top -= 1
return item
def peek(self):
if self.is_empty():
raise Exception("Stack is empty")
return self.stack[self.top]
def is_empty(self):
return self.top == -1
def size(self):
return self.top + 1
큐
연결 리스트 큐
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedListQueue:
def __init__(self):
self.front = None
self.rear = None
def is_empty(self):
return self.front is None
def enqueue(self, item):
new_node = Node(item)
if self.rear is None:
self.front = self.rear = new_node
return
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if self.front is None:
print("Queue is empty")
return None
item = self.front.data
self.front = self.front.next
if self.front is None:
self.rear = None
return item
def display(self):
current = self.front
result = []
while current:
result.append(current.data)
current = current.next
print(result)
디큐 (Deque)
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class LinkedListDeque:
def __init__(self):
self.front = None
self.rear = None
def push_front(self, item):
new_node = Node(item)
if self.front is None:
self.front = self.rear = new_node
else:
new_node.next = self.front
self.front.prev = new_node
self.front = new_node
def push_back(self, item):
new_node = Node(item)
if self.rear is None:
self.front = self.rear = new_node
else:
new_node.prev = self.rear
self.rear.next = new_node
self.rear = new_node
def pop_front(self):
if self.front is None:
print("Deque is empty")
return None
item = self.front.data
self.front = self.front.next
if self.front is None:
self.rear = None
else:
self.front.prev = None
return item
def pop_back(self):
if self.rear is None:
print("Deque is empty")
return None
item = self.rear.data
self.rear = self.rear.prev
if self.rear is None:
self.front = None
else:
self.rear.next = None
return item
def peek_front(self):
return self.front.data if self.front else None
def peek_back(self):
return self.rear.data if self.rear else None
트리
이진 트리
from collections import deque
def levelorder(node):
if not node:
return
queue = deque([node])
while queue:
current = queue.popleft()
print(current.value, end=' ')
# Current Node
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
이진 탐색 트리
class Node:
def __init__(self, val):
self.value = val
self.left = None
self.right = None
class BST:
def insert(self, node, val):
if not node:
return Node(val)
if val < node.value:
node.left = self.insert(node.left, val)
elif val > node.value:
node.right = self.insert(node.right, val)
return node
def search(self, node, val):
if not node or node.value == val:
return node
if val < node.value:
return self.search(node.left, val)
else:
return self.search(node.right, val)
def minValueNode(self, node):
current = node
while current.left:
current = current.left
return current
def delete(self, node, val):
if not node:
return node
if val < node.value:
node.left = self.delete(node.left, val)
elif val > node.value:
node.right = self.delete(node.right, val)
else:
if not node.left:
return node.right
elif not node.right:
return node.left
temp = self.minValueNode(node.right)
node.value = temp.value
node.right = self.delete(node.right, temp.value)
return node
def inorder(self, node):
if node:
self.inorder(node.left)
print(node.value, end=' ')
self.inorder(node.right)
AVL 트리
class Node:
def __init__(self, val):
self.value = val
self.left = None
self.right = None
self.height = 1
class AVL:
def getHeight(self, node):
return node.height if node else 0
def getBalance(self, node):
return (self.getHeight(node.left) - self.getHeight(node.right)) if node else 0
def rotateRight(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
x.height = 1 + max(self.getHeight(x.left), self.getHeight(x.right))
return x