[자료구조] 연결리스트와 트리 구조

1. 연결리스트 

0) 정의 

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

1) 구현 

· 노드 구현 

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 insertNode(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

2. 트라이 (Trie) 구조 

0) 정의

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

1) 구조

-> 문자열은 우리가 원하는 문자열로 시작할 수 있으며, 한 개의 트라이 구조의 가장 최상위 부모는 Null 값을 가짐 (Head)

2) 구현 

· 노드

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]

3) 활용 

· 추천검색어

-> 한 글자 한 글자 입력할 때 마다 이전 사용자들이 몇 번을 검색했는지에 대한 횟수를 가지고 있음.. 이를 활용하여 다음 문자 추천