[자료구조] 링크드 리스트 구현하기

노드

노드에는 2가지 정보가 필요하다.
1. 데이터
2. 다음 노드를 가리키는 값

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

• 위 2개의 데이터를 담기 위해 클래스를 선언해 담아주었다.

링크드 리스트

링크드 리스트 클래스는 head 노드(가장 앞의 노드)만을 가지고 있고, head 노드 부터 기차처럼 노드들이 추가되도록 구현!

class LinkedList:
    # 생성자
    def __init__(self, data):
        self.head = Node(data)

• 생성 시, 매개변수로 넘어오는 data를 Node로 만들고 head로 설정한다
  • 앞으로 링크드 리스트에 노드를 추가할 때 head의 뒤부터 노드가 추가된다.

링크드 리스트 추가 메소드

링크드 리스트 맨 뒤에 새로운 노드를 붙이는 메소드이다.

    # 추가
    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)

• 새로운 노드를 뒤에 붙이기 위해선, 노드의 끝까지 이동 후에 노드를 추가해야 한다.
  • while문을 사용해 노드의 맨 뒤로 이동한다.

링크드 리스트 조회 메소드

링크드 리스트의 모든 노드를 조회하는 메소드이다.

    # 출력
    def print_all(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next

• 노드의 데이터값을 찍으면서, while문을 통해 다음 노드로 넘어간다.

특정 인덱스의 노드 반환 메소드

매개변수로 인덱스를 넘겨주면, 링크드 리스트에서 해당하는 인덱스의 노드 값을 반환한다.

    # 특정 인덱스의 노드를 반환
    def get_node(self, index):
        if self.head is None:
            return None

        current_node = self.head
        current_index = 0          # 현재 노드의 인덱스

        while current_index < index:
            current_node = current_node.next
            current_index += 1
        return current_node

특정 인덱스에 노드 추가 메소드

    # 특정 인덱스에 노드 추가하는 메소드
    def add_node(self, index, data):
        if self.head is None:
            self.head = Node(data)
            return

        new_node = Node(data)  # 새로운 노드
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        node = self.get_node(index-1) # 인덱스의 노드
        next_node = node.next       # 인덱스의 다음 노드
        # 기존 노드들과 새 노드 연결하기
        node.next = new_node
        new_node.next = next_node

특정 인덱스의 노드 삭제 메소드

    # 특정 인덱스의 노드 삭제하는 메소드
        def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return

        node = self.get_node(index-1)
        # 노드 삭제 (연결 끊기)
        node.next = node.next.next

링크드 리스트의 특징은 뭐였지?
노드를 삭제할 때는 어떻게? 노드를 추가할 때는 어떤 식으로 흐름이 흘러갔지?를 생각하고, 도출해낸 방법을 코드로 옮겨적는 연습이 필요하지 않을까하는 생각이 들었다.
무작정 코드부터 작성하려 하니까 뭘 해야하는지, 어떻게 해야하는지 감이 1도 안오더라ㅎㅎ

일단 생각한 것을 글이나 그림으로 옮겨 적어보고, 맞다면 코드로 옮기기