자료구조 : 링크드 리스트 (Linked List)

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

• 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
• 노드(Node) : 데이터 저장 단위인 데이터값, 포인터로 구성
• 포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

 

링크드 리스트(Linked List) 형태

출처 : 위키피디아

 

Node 구현

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

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 = None(data)

node1 = Node(1)
head = node1
for index in range(2,10):
	add(index)

 

링크드 리스트 데이터 검색(출력)

node = head
while node.next:
	print(node.data)
    node = node.next
print (node.data) # 1부터 9까지 출력

 

링크드 리스트 장점과 단점

• 장점 : 배열은 데이터 공간을 미리 할당해야 하지만 링크드 리스트는 데이터 공간을 미리 할당하지 않아도 됨
• 단점 : 연결 정보를 찾는 시간이 필요, 접근하는 속도가 느림
           저장공간 효율이 높지 않음(연결을 위해 별도의 데이터 공간이 필요함)