[10주차] 연결 리스트와 트라이 구조

- 연결리스트 : LintedList, 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 데이터를 저장하는 자료 구조

 

- 리스트 : 데이터의 추가, 삭제 번거로움

 

<연결리스트>

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 = self.next
            now.next = node
            self.count += 1
            
            
    def insertNodeAtIndex(self, node, index):
    	if index < 0 or index > self.count:
        	return -1
        elif self.count == index:
        	self.append(node)
        elif index == 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
                first = second
                second = second.next
                
    def getCount(self):
    	return self.count

 

- 트라이 구조 : 문자열을 효율적으로 저장하고 탐색하기 위한 트리 형태의 자료구조

 

<트라이 구조>

class Node():
	def __init__(self, data):
    	self.data = data
        self.children = {}
        
class Trie():
	def __init__(self, data):
    	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]

- 트라이 구조 활용 : 추천 검색어