[자료구조 with Python] 링크드 리스트(Linked List)-1

링크드 리스트(Linked List)

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

용어

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

Node구현

• 노드 객체 생성

class Node:
	def __init__(self, data, next=None):
        self.data = data    	# 노드의 데이터
        self.next = next        # 노드의 포인터

• node와 node 연결

node1 = Node(1)        # 노드1 생성
node2 = Node(2)        # 노드2 생성
node1.next = node2        # 노드1의 포인터로 노드2를 연결
head = node1

• 링크드 리스트로 데이터 추가하는 메서드

# Node 클래스 안에 메서드 생성
def add(self, data):
	node = head        # 맨 앞에 노드
    # 노드의 포인터가 있을 때까지 = 포인터가 None이면 while문 끝
    while node.next:	   
        node = node.next
    node.next = Node(data)    # 끝에 연결
# 마지막 노드의 포인터에 새로운 노드를 연결하는 것!

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

node1 = Node(1)
head = node1
for index in range(2, 10):
    add(index)		# 1 2 3 4 5 6 7 8 9

• 링크드 리스트 데이터 출력

node = head
while node.next:
    print(node.data)
    node = node.next
print (node.data)
# 1 2 3 4 5 6 7 8 9