연결리스트/트라이

연결리스트와 트라이 자료구조에 대한 내용은 지난번에 컴퓨터공학 기초이론을 공부하며 나왔던 주제여서 해당 포스트에 내용이 정리되어 있다:

• [CS50] 6.자료구조, Data Structures

이번에는 연결리스트와 트라이 자료구조를 파이썬으로 구현하는 과정을 알아본다.

연결리스트

# 노드 구현
class Node():
	
	def __init__(self, data):
		self.data = data
		self.next = None

# 연결리스트 클래스
class LinkedList():
	
	# 초기생성자
	def __init__(self):
		self.head = None    # 연결리스트 시작점
		self.count = 0    # 노드의 갯수

	# 새 노드를 리스트 시작값으로 추가
	def appendHead(self, node):
		if self.head == None:    # 헤드가 없는 경우
			self.head = node    # 추가하는 노드를 헤드로 지정
			self.count = 1
		else:
			self.count += 1
			currentHead = self.head
			self.head = node
			node.next = currentHead

	# 새 노드를 추가
	def append(self, node)
		if self.head == None:    # 헤드가 없는 경우
			self.head = node
			self.count = 1
		else:
			now = self.head    # 헤드에서 시작
			while now.next != None:    # 현재 리스트의 끝부분으로 포인터 이동
				now = now.next
			now.next = node    # 마지막 노드의 다음 포인터 값으로 새 노드 지정
			self.count += 1

	# 중간에 새 노드 추가
	def insertNodeAtIndex(self, node, index):
		if index < 0 or index > self.count:    # 인덱스 값이 부정확하면 -1 반환
			return -1
		elif self.count == index:    # 인덱스 값이 리스트의 끝이라면 그냥 노드 추가 메서드 실행
			self.append(node)
		elif index == 0:    # 인덱스 값이 0이라면 (헤드) 시작값 추가 메서드 실행
			self.appendHead(node)
		else:
			now = self.head    # 헤드에서 시작
			while index > 0:    # 입력한 인덱스의 직전 노드까지 포인터 이동 
				index -= 1
				now = now.next
			self.count += 1
			next = now.next    # 밀려날 노드 포인터 저장
			now.next = node    # 다음 노드로 입력한 노드 지정 (포인터 값 변경)
			node.next = next   # 입력된 노드의 다음 노드로 밀려난 노드 지정

	# 노드 삭제
	def deleteData(self, data):
		if self.head.data == data:    # 삭제할 노드가 헤드라면
			self.head = self.head.next    # 다음 노드의 포인터 값을 헤드 값으로 저장
			self.count -= 1
		else:
			first = self.head
			second = first.next
			while second != None:    # 헤드에서 시작해서 삭제할 노드의 값까지 포인터 이동
				if second.data == data:
					first.next = second.next    # 삭제할 노드의 다음 포인터 값을 현재 노드의 포인터 값으로 저장
					self.count -= 1
					break

	# 연결리스트의 길이 반환
	def getCount(self):
		return self.count

트라이 (Trie)

# 노드 구현
class Node():

	def __init__(self, data):
		self.data = data
		self.children = {}

# 트라이 구현
class Trie():
	
	# 초기생성자
	def __init__(self):
		self.head = Node(None)
	
	# 문자리스트 추가
	def insert(self, string):
		head = self.head
		for s in string:
			children = head.children
			if s not in children:
				children[s] = Node(s)
			head = children[s]