TIL - Linked List 연결 리스트

문제

- 단순 연결 리스트(Singly Linked List)를 구현합니다.
- 노드는 값(data)과 다음 노드를 가리키는 포인터(next)를 가집니다.

 

문제풀이

class Node:
	# Node 구성 = data + next
    def __init__(self, data):
        self.data = data
        self.next = None


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

	# 리스트 끝에 노드 추가
    def append(self, data):
    	# 새 노드 생성
        new_node = Node(data)

		# 첫 노드 = head
        if self.head is None:
            self.head = new_node
            return 

		# current = 커서
        current = self.head
        
        # next 가 비어있으면
        while current.next is not None:
            current = current.next
        
        # next 자리에 새 노드 경로 연결
        current.next = new_node    
    

	# 리스트 값 반환
    def print_list(self):
        values = []
        current = self.head

        while current is not None:
            values.append(current.data)
            current = current.next
            
        return values

 

 

 

단일 연결 리스트

data, next 구조로 이루어져 있으며 next 는 다음에 연결된 노드의 경로를 담고 있다. 

 

    """
    연결 리스트의 노드 (한 칸 = 데이터 + 다음 화살표)

        ┌──────┬──────┐
        │ data │ next │ ──▶ (다른 Node 또는 None)
        └──────┴──────┘
    """

 

 

어려웠던 점

1. next 에 경로를 어떻게? 담고있는지 python 의 데이터 주소와... 그런 메모리? 할당? 이런것들이 헷갈린다.
2. 단일 연결 리스트 구조는 이해함