[자료구조/알고리즘] 연결 리스트(Linked List), 더블 연결 리스트(Double Linked List), 트라이 구조(Trie)

리스트란?

• 데이터를 인덱스 값에 따라 저장
• 대량의 데이터에서 추가와 삭제 시 성능이 저하된다.

연결 리스트란?

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

 

[링크드 리스트 (Linked List) 구조]
* 연결 리스트라고도 함
* 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
* 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원'

 

[링크드 리스트 기본 구조와 용어]
  - 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성
  - 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

 

[Node 구현]
- 보통 파이썬에서 링크드 리스트 구현시, 파이썬 클래스를 활용함
  - 파이썬 객체지향 문법 이해 필요
  - 참고: https://www.fun-coding.org/PL&OOP1-3.html

파이썬과 객체지향 프로그래밍: 객체지향 (class와 object) - 잔재미코딩

 

 

[링크드 리스트의 장단점 (전통적인 C언어에서의 배열과 링크드 리스트)]
* 장점
  - 미리 데이터 공간을 미리 할당하지 않아도 됨
  - 배열은 미리 데이터 공간을 할당 해야 함
* 단점
  - 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
  - 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
  - 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

 

[링크드 리스트의 복잡한 기능1 (링크드 리스트 데이터 사이에 데이터를 추가)]
- 링크드 리스트는 유지 관리에 부가적인 구현이 필요함

 

 

 

#패스트캠퍼스
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
    
class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        
    def add(self, data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
        
    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next
    
    def delete(self, data):
        if self.head == '':
            print ("해당 값을 가진 노드가 없습니다.")
            return
        
        if self.head.data == data:
            temp = self.head
            self.head = self.head.next
            del temp
        else:
            node = self.head
            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    return
                else:
                    node = node.next
        
#class 밖의 add 함수 (참고용)
def add(data):
    node = head
    while node.next:
        node = node.next
    node.next = Node(data) 


#링크드리스트 생성
node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1

for index in range(3, 10):
    add(index)
    
    
#링크드리스트 조회
node = head
while node.next:
    print(node.data)
    node = node.next
print (node.data)


#노드 삽입
node3 = Node(1.5)

node = head
search = True
while search:
    if node.data == 1:
        search = False
    else:
        node = node.next

node_next = node.next
node.next = node3
node3.next = node_next

#링크드리스트 생성
linkedlist1 = NodeMgmt(0)

#노드 추가
for data in range(1, 10):
    linkedlist1.add(data)

#링크드리스트 존재 여부 확인
linkedlist1.head

#노드 삭제
linkedlist1.delete(4)

#링크드리스트 조회
linkedlist1.desc()

 

#엔코아
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:
		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

---

* 더블 링크드 리스트(Doubly linked list) 기본 구조 
  - 이중 연결 리스트라고도 함
  - 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능

 

class Node:
    def __init__(self, data, prev=None, next=None):
        self.prev = prev
        self.data = data
        self.next = next

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head
    
    def insert_before(self, data, before_data):
        if self.head == None:
            self.head = Node(data)
            return True            
        else:
            node = self.tail
            while node.data != before_data:
                node = node.prev
                if node == None:
                    return False
            new = Node(data)
            before_new = node.prev
            before_new.next = new
            new.next = node
            return True

    def insert_after(self, data, after_data):
        if self.head == None:
            self.head = Node(data)
            return True            
        else:
            node = self.head
            while node.data != after_data:
                node = node.next
                if node == None:
                    return False
            new = Node(data)
            after_new = node.next
            new.next = after_new
            new.prev = node
            node.next = new
            if new.next == None:
                self.tail = new
            return True

    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next
            
            
double_linked_list = NodeMgmt(0)
for data in range(1, 10):
    double_linked_list.insert(data)
double_linked_list.desc()

node_3 = double_linked_list.search_from_tail(3)
node_3.data

double_linked_list.insert_before(1.5, 2)
double_linked_list.desc()

node_mgmt.insert_after(1.5, 1)
node_mgmt.desc()

---

트라이(Trie) 구조란?

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]

트라이 구조 활용