[Python] 사전만들기 (Linked List)

Sony·2022년 8월 2일

python 자료구조

📚 자료구조

목록 보기

6/6

📌 What to do?

주어진 사전 파일의 단어들을 연결리스트로 담아 사전 프로그램을 만든다.

⚡️ 단어 사전 파일

randdict.txt 파일에는 약 5만개의 단어와 그 뜻이 저장되어 있다. 저장된 순서는 없다.
단어와 단어의 뜻은 " : " 으로 구분되어 있다. (ex. apple : 사과)

⚡️ 단어 사전 데이터로 연결리스트 만들기

자료형은 연결 리스트를 이용한다.
사전의 단어들을 연결리스트에 추가할 때에는 알파벳 순으로 정렬된 상태로 저장한다.

완성된 프로그램의 실행 예시는 다음과 같다.

📌 연결리스트를 어떤 형태로 만들 것인가?

이중 연결리스트로 만들었다.

⚡️ Why?

우선 해당 연결 리스트는 사전의 단어들이 ‘정렬된’상태로 저장되어야 한다.
이를 위해 단일 연결 리스트는 새로운 단어가 추가될 때 마다 head부터 탐색하여 해당 단어가
들어갈 위치를 찾아야한다. (정렬된 상태를 유지해야 하므로)
이는 매우 비효율적이고 동시에 많은 높은 시간 복잡도를 요하는 방식이란 생각이 들어 더 나
은 자료 구조가 없는지 생각해 보았다.
그렇게 생각해낸 것이 ‘이중 연결 리스트’였다.
이중 연결 리스트는 head나 tail이 아닌 내가 원하는 특정한 지점(ex. 중간, 1/3 지점, 1/4지점…)
의 위치 정보를 저장해두고, 해당 위치를 기준으로 탐색을 수행할 수 있어 단일 연결 리스트 보
다 효율적인 방식이란 생각이 들었다.
그리고 실제로 이를 위해 head와 tail 외에 mid, 즉 연결 리스트의 중간 위치를 반환하는 변수
를 따로 설정해 주었고, 이를 기준점으로 삼아 탐색을 수행하도록 하였다.

🛠 Doubly Linked List class

class dbList:
	def __init__(self):
		self.head = None 		# 링크드 리스트의 가장 앞 노드
		self.tail = None 		# 링크드 리스트의 가장 뒤 노드
		self.mid = None 		# 링크드 리스트의 중간 위치 노드
        self.pos = 0 			# mid 의 위치를 조정하기 위한 flag
        self.size = 0 			# 링크드 리스트의 노드의 개수

head(맨 앞), tail(맨 뒤) 변수 외에도 mid(중간) 변수를 선언한 것을 확인할 수 있다.
또한 mid의 위치를 연결 리스트의 중앙으로 조정해주기 위한 변수 pos와
연결 리스트의 전체 node의 개수를 나타내는 size변수도 선언하였다.

🛠 class Node

class Node:
	def __init__(self, data):
		self.data = data # 실제 노드가 저장하는 데이터
		self.next = None # 다음 노드에 대한 레퍼런스
		self.prev = None # 전 노드에 대한 레퍼런스

노드가 저장하는 데이터(단어와 그 뜻) data,
현재 노드의 다음 노드에 대한 레퍼런스를 나타내는 변수 next,
그리고 다음 노드에 대한 레퍼런스를 나타내는 변수 prev를 선언하였다.

🛠 isEmpty( )

def isEmpty(self):
	if self.size != 0:
		return False
	else:
		return True

연결 리스트가 비어 있는지 판단해주는 메소드이다.

🛠 insert( )

def insert(self, pre, data):
	new_node = Node(data)
    
	if pre is self.tail: 			# 가장 마지막 순서 삽입
		self.tail.next = new_node
		new_node.prev = self.tail
		self.tail = new_node
	else: 							# 두 노드 사이에 삽입
		new_node.prev = pre
		new_node.next = pre.next
		pre.next.prev = new_node
		pre.next = new_node
        
	self.size += 1

연결 리스트의 원하는 위치에 노드를 삽입해주는 메소드이다.
삽입할 노드의 데이터(data)와 삽입할 위치 앞의 노드(pre)의 위치를 매개변수로 받는다.

🛠 append( )

def append(self, data):
	new_node = Node(data)
    
	if self.isEmpty():
		self.head = new_node
		self.tail = new_node
		self.mid = new_node
	else:
		temp = self.head
		self.head = new_node
		temp.prev = self.head
		new_node.next = temp
        
	self.size += 1

비어 있는 연결 리스트, 혹은 비어 있지 않은 연결리스트의 맨 앞에 노드를 삽입하는 메소드이다.

📌 어떻게 제공된 사전 파일의 단어들을 정렬된 형태의 연결리스트로 만들 것인가?

🛠 makeDict( )

def makeDict(self, data):

randdict의 단어들을 순서대로 가져와 정렬한 채로 링크드 리스트에 넣어 주는 메소드이다.
이 메소드의 작동 방식은 다음과 같다.

iterator = self.mid

우선 연결 리스트를 돌아다니며 새로운 단어가 추가 될 위치를 탐색하게 될 변수 iterator를 선언
해주고, 해당 변수의 위치를 연결리스트의 중앙(mid)으로 초기화 시켜준다.

앞서 설명했던 대로 매번 연결 리스트의 맨 앞부터 탐색하는 것보단
중앙에서 탐색을 시작하는 것이 보다 효율적일 것 같다고 생각하여 위와 같은 과정을 수행하였다.

그리고는 케이스를 분류하여 각 케이스마다 알맞은 작업을 수행하였다.

⚡️ Case

1) 리스트가 비어 있을 경우

append 메소드로 새로운 단어를 추가해준다.

2) 리스트가 비어 있지 않을 경우

2-1) 추가될 단어가 iterator 위치에 해당하는 단어 보다 작을 때 (알파벳 순서상 앞에 위치)

a. iterator 앞에 노드가 없을 경우

리스트의 맨 앞에 해당 단어 바로 추가 (by append 메소드)

b. 추가될 단어가 iterator.prev에 해당하는 단어 보다 작을 경우

iterator 위치 왼쪽으로 한 칸 이동

c. 추가될 단어가 iterator.prev에 해당하는 단어 보다 클 경우 (알파벳 순서상 뒤에 위치)

iterator 와 iterator.prev 사이에 해당 단어 삽입 (by insert 메소드)

d. 추가될 단어가 iterator.prev에 해당하는 단어와 같을 경우
(randdict에는 중복된 단어가 존재하지 않는데 위와 같은 경우가 발생하는 이유는 lower( )함수를
사용하여 모든 단어를 소문자로 변환한 뒤 해당 단어들을 비교하기 때문이다.)

d-1) lower를 떼고 비교 했을 때, 추가될 단어가 iterator.prev에 해당하는 보다 작을 경우

iterator.prev 앞에 노드가 없을 경우 : 리스트의 맨 앞에 해당 단어 바로 추가
아닐 경우 : iterator.prev 와 iterator.prev.prev 사이에 해당 단어 삽입

d-2) lower를 떼고 비교 했을 때, 추가될 단어가 iterator.prev에 해당하는 보다 클 경우

iterator 와 iterator.prev 사이에 해당 단어 삽입

2-2) 추가될 단어가 iterator 위치에 해당하는 단어 보다 클 때

a. iterator 뒤에 노드가 없을 경우

리스트의 맨 뒤에 해당 단어 바로 추가 (by insert 메소드)

b. 추가될 단어가 iterator.next에 해당하는 단어 보다 클 경우

iterator 위치 오른쪽으로 한 칸 이동

c. 추가될 단어가 iterator.next에 해당하는 단어 보다 작을 경우

iterator 뒤에 해당 단어 삽입 (by insert 메소드)

d. 새로 추가될 단어가 iterator.next에 해당하는 단어와 같을 경우

d-1) lower를 떼고 비교 했을 때, 추가될 단어가 iterator.next에 해당하는 단어보다 작을 경우

iterator.next 뒤에 해당 단어 삽입

d-2) lower를 떼고 비교 했을 때, 추가될 단어가 iterator.next에 해당하는 단어보다 클 경우

iterator.next 뒤에 해당 단어 삽입

3) pos값의 변화

앞서 설명한대로 pos는 mid의 위치를 연결 리스트의 중앙으로 조정해주기 위한 변수이다.

size가 짝수일때는 이 pos의 값이 0, -1 혹은 +1이면 iterator의 위치가 mid(중앙)이고,
홀수일때는 pos의 값이 0이면 iterator의 위치가 mid(중앙)이다.

해당 작업이 잘 수행되도록 하기 위해 iterator, 즉 mid가 연결리스트의 왼쪽으로 이동할 경우엔
pos에 -1을, 오른쪽으로 이동할 경우엔 pos에 +1을 해준다.

이는 곧 mid를 기준으로 왼쪽과 오른쪽의 균형을 맞춰주는 것을 의미한다.
그러다 균형이 깨지면 (pos = -2 or pos = +2) 다음과 같은 작업을 수행한다.

pos = -2 : mid를 왼쪽으로 한 칸 이동 & pos = 0
pos = +2 : mid를 오른쪽으로 한 칸 이동 & pos = 0

위와 같은 과정들을 통해 mid의 위치를 계속하여 연결리스트의 중앙으로 유지시킬 수 있다.

📌 단어 검색 & 단어 추가 기능은 어떻게 구현할 것인가?

🛠 search( )

def search(self, target):

연결 리스트에서 원하는 단어를 탐색하기 위한 메소드이다.
해당 메소드도 마찬가지로 연결리스트의 중간부터 탐색을 시작한다.
그리고는 케이스를 분류하여 각 케이스마다 알맞은 작업을 수행하였다.

⚡️ Case

1) 찾고자 하는 단어가 iterator에 해당하는 단어와 같을 경우 (lower( )를 수행한 값)

a. lower를 떼고 비교 했을 때, 찾고자 하는 단어가 iterator에 해당하는 단어와 같을 경우

iterator에 해당하는 단어의 뜻 출력

b. lower를 떼고 비교 했을 때, 찾고자 하는 단어가 iterator 보다 작을 경우

iterator 위치 왼쪽으로 한 칸 이동

b-1) 이동한 위치에 해당하는 단어와 찾고자 하는 단어가 일치할 경우

iterator에 해당하는 단어의 뜻 출력

b-2) 이동한 위치에 찾고자 하는 단어가 없을 경우

newWord 메소드 호출

c. lower를 떼고 비교 했을 때, 찾고자 하는 단어가 iterator 보다 클 경우

iterator 위치 오른쪽으로 한 칸 이동

c-1) 이동한 위치에 해당하는 단어와 찾고자 하는 단어가 일치할 경우

iterator에 해당하는 단어의 뜻 출력

c-2) 이동한 위치에 찾고자 하는 단어가 없을 경우

newWord 메소드 호출

2) 찾고자 하는 단어가 iterator에 해당하는 단어 보다 작을 경우

a. iterator 앞에 노드가 없을 경우

newWord 메소드 호출

찾고자 하는 단어가 연결 리스트 상에 존재하지 않는 경우이기 때문이다.

b. 찾고자 하는 단어가 iterator.prev에 해당하는 단어 보다 클 경우

newWord 메소드 호출

이 또한 찾고자 하는 단어가 연결 리스트 상에 존재하지 않는 경우이다.
왜냐하면 이는 target을 찾아 특정 방향으로 탐색을 계속해서 진행하다가(one way)
한번 그 방향이 반대 방향으로 틀어졌음, 즉 target이 연결 리스트 상에 존재하지 않음을 의미하기 때문이다.

c. 위의 경우들에 해당하지 않는다면

iterator 위치 왼쪽으로 한 칸 이동

3) 찾고자 하는 단어가 iterator에 해당하는 단어 보다 클 경우

a. iterator 뒤에 노드가 없을 경우

newWord 메소드 호출

찾고자 하는 단어가 연결 리스트 상에 존재하지 않는 경우이기 때문이다.

b. 찾고자 하는 단어가 iterator.next에 해당하는 단어 보다 작을 경우

newWord 메소드 호출

c. 위의 경우들에 해당하지 않는다면

iterator 위치 오른쪽으로 한 칸 이동

🛠 newWord( )

def newWord(self, inputWord):

찾고자 하는 단어가 없을 경우, 해당 단어를 연결 리스트에 추가해주는 메소드이다.

📌 실행결과

📌 전체코드

"""Node 클래스"""
class Node:
    def __init__(self, data):
        self.data = data        # 실제 노드가 저장하는 데이터
        self.next = None        # 다음 노드에 대한 레퍼런스
        self.prev = None        # 전 노드에 대한 레퍼런스

"""더블 링크드 리스트 클래스"""
class dbList:
    def __init__(self):
        self.head = None    # 링크드 리스트의 가장 앞 노드
        self.tail = None    # 링크드 리스트의 가장 뒤 노드
        self.mid = None     # 링크드 리스트의 중간 위치 노드
        self.pos = 0        # mid의 위치를 조정하기 위한 flag
        self.size = 0       # 링크드 리스트의 노드의 개수

    """링크드 리스트가 비어 있는지 판단하는 메소드"""
    def isEmpty(self):
        if self.size != 0:
            return False
        else:
            return True

    """링크드 리스트의 원하는 위치에 노드를 삽입하는 메소드"""
    # 삽입할 노드의 데이터와 삽입할 위치 앞의 노드(pre)의 위치를 매개변수로 받는다
    def insert(self, pre, data):
        new_node = Node(data)

        if pre is self.tail:            # 가장 마지막 순서 삽입
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        else:                           # 두 노드 사이에 삽입
            new_node.prev = pre
            new_node.next = pre.next
            pre.next.prev = new_node
            pre.next = new_node
        self.size += 1

    """비어 있는 링크드 리스트, 혹은 비어 있지 않은 리스트의 맨 앞에 노드를 삽입하는 메소드"""
    def append(self, data):
        new_node = Node(data)

        if self.isEmpty():            # 링크드 리스트가 비어 있을때
            self.head = new_node
            self.tail = new_node
            self.mid = new_node
        else:                         # 비어 있지 않을때 : 리스트의 맨 앞에 노드 삽입
            temp = self.head
            self.head = new_node
            temp.prev = self.head
            new_node.next = temp
        self.size += 1

    """randdict의 단어들을 순서대로 가져와 정렬한 채로 링크드 리스트에 넣어 주는 메소드"""
    def makeDict(self, data):
        if self.isEmpty():                                                     # 리스트가 비어 있을 경우
            self.append(data)
        else:                                                                   # 리스트가 비어 있지 않을 경우
            iterator = self.mid                                                 # 리스트의 중간부터 새로 추가될 단어가 삽입될 위치 탐색
            if data[0].lower() < iterator.data[0].lower():                      # data[0]이 mid.data[0] 보다 작을 때
                while True:
                    if iterator.prev is None:                                   # iterator 앞에 노드가 없을 경우
                        self.append(data)                                       # 리스트의 맨 앞에 바로 추가
                        break
                    elif data[0].lower() < iterator.prev.data[0].lower():       # 새로 추가될 단어가 iterator.prev 보다 작을 경우 (알파벳 순서상 앞에 위치)
                        iterator = iterator.prev                                # iterator 위치 한칸 앞으로 이동
                    elif data[0].lower() > iterator.prev.data[0].lower():       # 새로 추가될 단어가 iterator.prev 보다 클 경우 (알파벳 순서상 뒤에 위치)
                        self.insert(iterator.prev, data)                        # iterator 와 iterator.prev 사이에 해당 단어 삽입
                        break
                    elif data[0].lower() == iterator.prev.data[0].lower():      # 새로 추가될 단어가 iterator.prev 와 같을 경우 (lower() 때문에)
                        if data[0] < iterator.prev.data[0]:                     # 원본으로 복구 시켜 비교했을때, 새로 추가될 단어가 iterator.prev 보다 작을 경우(알파벳 순서상 앞에 위치)
                            if iterator.prev.prev is None:                      # iterator.prev 앞에 노드가 없을 경우
                                self.append(data)                               # 리스트의 맨 앞에 바로 추가
                                break
                            else:
                                self.insert(iterator.prev.prev, data)           # 아닐 경우엔 iterator.prev 와 iterator.prev.prev 사이에 해당 단어 삽입
                                break
                        elif data[0] > iterator.prev.data[0]:                   # 원본으로 복구 시켜 비교했을때, 새로 추가될 단어가 iterator.prev 보다 클 경우(알파벳 순서상 뒤에 위치)
                            self.insert(iterator.prev, data)                    # iterator 와 iterator.prev 사이에 해당 단어 삽입
                            break
                self.pos -= 1                                                   # 링크드 리스트의 왼쪽으로 이동할 경우엔 pos에 -1

            else:                                                               # data[0]이 mid.data[0] 보다 클 때
                while True:
                    if iterator.next is None:                                   # iterator 뒤에 노드가 없을 경우
                        self.insert(iterator, data)                             # 리스트의 맨 뒤에 바로 추가
                        break
                    elif data[0].lower() > iterator.next.data[0].lower():       # 새로 추가될 단어가 iterator.next 보다 클 경우 (알파벳 순서상 뒤에 위치)
                        iterator = iterator.next                                # iterator 위치 한칸 뒤로 이동
                    elif data[0].lower() < iterator.next.data[0].lower():       # 새로 추가될 단어가 iterator.next 보다 작을 경우 (알파벳 순서상 앞에 위치)
                        self.insert(iterator, data)                             # iterator 뒤에 해당 단어 삽입
                        break
                    elif data[0].lower() == iterator.next.data[0].lower():      # 새로 추가될 단어가 iterator.next 와 같을 경우 (lower() 때문에)
                        if data[0] < iterator.next.data[0]:                     # 원본으로 복구 시켜 비교했을때, 새로 추가될 단어가 iterator.next 보다 작을 경우 (알파벳 순서상 앞에 위치)
                            self.insert(iterator, data)                         # iterator 뒤에 해당 단어 삽입
                            break
                        elif data[0] > iterator.next.data[0]:                   # 원본으로 복구 시켜 비교했을때, 새로 추가될 단어가 iterator.next 보다 클 경우 (알파벳 순서상 뒤에 위치)
                            self.insert(iterator.next, data)                    # iterator.next 뒤에 해당 단어 삽입
                            break
                self.pos += 1                                                   # 링크드 리스트의 오른쪽으로 이동할 경우엔 pos에 +1

            """mid 위치 설정 : pos의 값이 0일때의 mid의 위치가 링크드 리스트의 중앙이다."""
            if self.pos == 2:               # pos가 2가 되면
                self.mid = self.mid.next    # mid를 오른쪽으로 이동
                self.pos = 0                # pos값 다시 0으로
            elif self.pos == -2:            # pos가 -2가 되면
                self.mid = self.mid.prev    # mid를 왼쪽으로 이동
                self.pos = 0                # pos값 다시 0으로

    """링크드 리스트에서 원하는 단어를 탐색하기 위한 메소드"""
    def search(self, target):
        iterator = self.mid                                             # 리스트의 중간부터 찾고자 하는 단어(target) 탐색 시작
        while True:
            if target.lower() == iterator.data[0].lower():              # 찾고자 하는 단어가 iterator 와 같을 경우 (lower() 때문에)
                if target == iterator.data[0]:                          # 원본으로 복구 시켜 비교했을때, 찾고자 하는 단어가 iterator 와 같을 경우
                    print(iterator.data[1])                             # iterator에 해당하는 단어의 뜻 출력
                    break
                elif target < iterator.data[0]:                         # 찾고자 하는 단어가 iterator 보다 작을 경우 (알파벳 순서상 앞에 위치)
                    iterator = iterator.prev                            # iterator 위치 한칸 앞으로 이동
                    if target == iterator.data[0]:                      # 찾고자 하는 단어가 iterator(이동 한 위치) 와 같을 경우
                        print(iterator.data[1])                         # iterator에 해당하는 단어의 뜻 출력
                        break
                    else:                                               # 찾고자 하는 단어가 없을 경우
                        self.newWord(target)                            # newWord 메소드 호출
                        break
                else:                                                   # 찾고자 하는 단어가 iterator 보다 클 경우 (알파벳 순서상 뒤에 위치)
                    iterator = iterator.next                            # iterator 위치 한칸 뒤로 이동
                    if target == iterator.data[0]:                      # 찾고자 하는 단어가 iterator(이동 한 위치) 와 같을 경우
                        print(iterator.data[1])                         # iterator에 해당하는 단어의 뜻 출력
                        break
                    else:                                               # 찾고자 하는 단어가 없을 경우
                        self.newWord(target)                            # newWord 메소드 호출
                        break
            elif target.lower() < iterator.data[0].lower():             # 찾고자 하는 단어가 iterator 보다 작을 경우 (알파벳 순서상 앞에 위치)
                if iterator.prev is None:                               # iterator 앞에 노드가 없을 경우
                    self.newWord(target)                                # newWord 메소드 호출
                    break
                elif target.lower() > iterator.prev.data[0].lower():    # 찾고자 하는 단어가 iterator.prev 보다 클 경우 (알파벳 순서상 뒤에 위치)
                    self.newWord(target)                                # newWord 메소드 호출 -> 튕겨져 나온 경우 이므로 찾는 단어가 없다는 의미이다
                    break
                else:                                                   # 위의 경우들에 해당하지 않는다면
                    iterator = iterator.prev                            # iterator 위치 한칸 앞으로 이동
            else:                                                       # 찾고자 하는 단어가 iterator 보다 클 경우 (알파벳 순서상 뒤에 위치)
                if iterator.next is None:                               # iterator 뒤에 노드가 없을 경우
                    self.newWord(target)                                # newWord 메소드 호출
                    break
                elif target.lower() < iterator.next.data[0].lower():    # 찾고자 하는 단어가 iterator.next 보다 작을 경우 (알파벳 순서상 앞에 위치)
                    self.newWord(target)                                # newWord 메소드 호출 -> 튕겨져 나온 경우 이므로 찾는 단어가 없다는 의미이다
                    break
                else:                                                   # 위의 경우들에 해당하지 않는다면
                    iterator = iterator.next                            # iterator 위치 한칸 뒤로 이동

    """찾고자 하는 단어가 없을 경우, 해당 단어를 추가하는 메소드"""
    def newWord(self, inputWord):
        print('찾을 수 없는 단어입니다. 뜻을 추가하세요(추가하지 않으려면 공백)')
        inputMean = input('> ')

        if inputMean == '':
            pass
        else:
            newData = [inputWord, inputMean]
            self.makeDict(newData)
            print(newData[0], newData[1], '가 추가되었습니다.(총 %d개 단어)' % self.size)

f = open('randdict_utf8.TXT', 'r')
dict = dbList()                            # randdict의 단어를 가져와 담아 줄 링크드 리스트

while True:
    line = f.readline()
    if line == '':
        break
    word = line[:line.find(':') - 1]      # 단어
    mean = line[line.find(':') + 2:-1]    # 단어의 뜻
    data = [word, mean]                   # [단어, 뜻]
    dict.makeDict(data)
f.close()

while True:
    target = input(">>")
    dict.search(target)