[Python] 링크드 리스트 (Linked List)

링크드 리스트 (Linked List)

 

1. 링크드 리스트 (Linked List) 구조

: 연결 리스트라고도 함

: 배열을 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조

: 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조

: 본래 C언어에서는 주요한  데이터 구조이다. 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원한다.

: 링크드 리스트의 기본 구조와 용어

• 노드(Node) : 데이터 저장 단위 (데이터 값, 포인터)로 구성
• 포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

2. 간단한 링크드 리스트 예

Node 구현

\(\rightarrow\) 파이썬에서는 링크드 리스트 구현 시 class를 활용

# 1
class Node:
	def __init__(self, data):
		self.data = data
		self.next = None
# 2
class Node:
	def __init__(self, data, next=None):
		self.data = data
		self.next = next

Node와 Node 연결 (포인터 활용)

node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1

링크드 리스트로 데이터 추가

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

	def add(data):
		node = head
		while node.next:
			node = node.next
		node.next = Node(data)

 

3. 링크드 리스트의 장단점

장점

• 데이터 공간을 미리 할당할 필요가 없다.

단점

• 연결을 위한 별도 데이터 공간이 필요하므로, 저장 공간 효율이 높지 않다.
• 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다.
• 중간 데이터 삭제 시, 앞 뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요하다.

 

4. 링크드 리스트의 복잡한 기능 (링크드 리스트 데이터 사이에 데이터를 추가)

\(\rightarrow\) 링크드 리스트는 유지 관리에 부가적인 구현이 필요.

# 1 ~ 10 사이에서 1과 2사이에 다음 노드를 추가하고 싶다.
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

 

5. 파이썬의 객체 지향 프로그래밍으로 링크드 리스트 구현하기

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
			def temp
		else:
			node = self.head
			while node.next:
				if node.next.data == data:
					temp = node.next
					node.next == node.next.next
					del temp
				else:
					node = node.next
	
	def search_node(self, data):
		node = self.head
		while node:
			if node.data == data:
				return node
			else:
				node = node.next

 

7. 더블 링크드 리스트 (Doubly Linked List) 기본 구조

: 이중 연결 리스트라고도 한다.

: 양방향으로 연결되어 있어 노드 탐색이 양쪽으로 모두 가능하다.

https://www.geeksforgeeks.org/doubly-linked-list/

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

class NodeMgmt:
	def __init__(self, data):
		self.head = Node(data)
		self.tail = self.head

	def insert(self, data):
		if self.head == None:
			self.head = Node(data)
			self.tail = self.head
		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

	def search_from_head(self, data):
		if self.head == None:
			return False

		node = self.head

		while node:
			if node.data == data:
				return node
			else:
				node = node.next
		return False
		
	def search_from_tail(self, data):
		if self.head == None:
			return False

		node = self.head

		while node:
			if node.data == data:
				return node
			else:
				node = node.prev
		return False
	
	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.prev = before_new
			new.next = node
			node.prev = new
			return True