링크드 리스트 구현 - 1

[Linked List의 생김새]

노드가 연결되어있는 생김새

linked_list = ["노드1"] -> ["노드2"] -> ["노드3"] -> ["노드4"]

 

[노드가 필요한 정보]

1. 칸에 있는 데이터

2. 다음 칸이 뭔지

 

클래스의 생성자에 data를 인자로 받아서 self.data에 값을 저장

다음 노드가 이어지는게 없기 때문에 self.next에는 None을 넣어두기

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

노드 생성 및 연결

node = Node(3)
first_node = Node(4)
node.next = first_node  # node의 next 변수에 first_node의 주소값 저장

 

데이터 3이 들어있는 노드에 4가 들어있는 노드를 연결해 현재는

[3] -> [4]

이렇게 연결되어있는 상태임

 

하지만 위의 과정을 100번, 1000번, ... 반복하게 된다면 너무 힘듦...

이걸 해결할 수 있는 방법은 Linked List !!!!

Linked List는 head 노드(맨 앞에 있는 노드)만 가지고 있음

다음 노드를 보기 위해서 노드 클래스의 next를 통해 다음 노드에 접근해야함 

 

[Linked List]

1. self.head에 시작하는 노드 저장

2. 다음 노드를 보기 위해 각 노드의 next를 조회해서 찾아가야함

 

[self.head에 시작하는 노드 저장]

class LinkedList:
    def __init__(self, data):
        # 인수 data의 값을 가지고 있는 노드를 새로 만들어서 head에 저장
        self.head = Node(data)

링크드리스트의 가장 첫번째 노드를 만듦

linked_list = LinkedList(5)
print(linked_list.head.data)  # 5

 

 

[노드에 새 노드를 이어 붙이는 append 함수 만들기]

    " 다음 노드를 보기 위해 각 노드의 next를 조회해서 찾아가야함! "

    next 변수 값이 None인 노드를 찾을 때까지

    이미 만들어져있는 노드에 저장되어있는 next 변수로 다음 노드를 찾아찾아가

    그 뒤에다가 새 노드를 붙임

    (next 변수 값이 None인 노드면, Linked List의 맨 끝에 위치해있는 노드임)

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

    # 다음 노드를 보기 위해 각 노드의 next를 조회해서 찾아가야함
    def append(self, data):
        # head가 비어있는 경우를 대비
        if self.head is None:
            self.head = Node(data)
            return

        current_node = self.head   # 맨 앞에 있는 노드
        while current_node.next is not None:  # next변수에 값이 존재하는 동안에 반복
            current_node = current_node.next  # 다음 노드로 이동
        current_node.next = Node(data)        # 맨 뒤에 있는 노드에 새 노드 연결

 

linked_list = LinkedList(5)
linked_list.append(12)
# 이렇게 되면 5 -> 12 형태로 노드를 연결한 겁니다!
linked_list.append(8)
# 이렇게 되면 5 -> 12 -> 8 형태로 노드를 연결한 겁니다!

 

[모든 원소를 출력하는 print_all 함수 만들기]

head에 저장되어있는 노드를 cur 라는 변수에 담고, cur 의 data를 출력

cur의 next 값을 cur 에 대입하고 그 값을 출력

이 과정을 cur 이 None 이 아닐때까지 반복

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

    def append(self, data):
        if self.head is None:
            self.head = Node(data)
            return
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
        current_node.next = Node(data)

    # 노드들의 값들을 전부 출력
    def print_all(self):
        # head 노드가 없을 경우를 대비
        if self.head is None:
            print("Node is None")
            return
        # 값이 없는 next 변수를 찾을 때 까지 각 노드에 있는 값(변수 data) 출력
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next