Linked List (연결 리스트)

연결 리스트는 각 노드마다 데이터와 다음 노드의 메모리 주소값이 있는 구조입니다.

https://www.geeksforgeeks.org/data-structures/linked-list/singly-linked-list/

이 구조는 블록체인의 구조와도 아주 약간 비슷하네요.(데이터가 있고, 그 데이터 해쉬값이 다음 노드에 넘어온다는 점)

 

연결 리스트는 데이터를 읽는데 시간이 걸립니다.(O(n))(head부터 읽어와야 합니다.)

하지만 삽입과 삭제에는 배열보다 속도가 빠릅니다.(배열은 삭제 후 다시 index정렬)(연결 리스트는 주소만 바꾸면 됨)

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


class LinkedList:
	def __init__(self):
		self.head = None
		self.last_node = None

	# function to add elements to linked list
	def append(self, data):
		# if linked list is empty then last_node will be none so in if condition head will be created
		if self.last_node is None:
			self.head = Node(data)
			self.last_node = self.head
		# adding node to the tail of linked list
		else:
			self.last_node.next = Node(data)
			self.last_node = self.last_node.next

# function to print the content of linked list
	def display(self):
		current = self.head
	# traversing the linked list
		while current is not None:
		# at each node printing its data
			print(current.data, end=' ')
		# giving current next node
			current = current.next
		print()

# Driver code
if __name__ == '__main__':
	L = LinkedList()
	# adding elements to the linked list
	L.append(1)
	L.append(2)
	L.append(3)
	# displaying elements of linked list
	L.display()

이 외에도 Doubly Linked List(이중 연결 리스트)(다음 노드뿐 아니라 그 전 노드의 주소값도 가지고 있습니다.)

Circular Linked List(원형 연결 리스트)(tail이 head의 주소값을 가지고 있습니다.)

 

참조 : https://www.geeksforgeeks.org/types-of-linked-list/

Types of Linked List - GeeksforGeeks