링크드 리스트 구현 - 2

[Linked List에서 index번째 원소를 반환하기]

현재의 index(current_index)가 매개변수 index 값과 같아질 때까지

노드를 한 칸씩 이동하면서, 한 칸 이동할 때 현재의 index값을 1씩 증가시킴

    def get_node(self, index):
        current_index = 0
        current_node = self.head
        while current_index < index:
            current_node = current_node.next
            current_index += 1
        return current_node

 

 

 

[내가 만든 get_node 함수]

노드를 한 칸 이동한 즉시 현재index(current_index)와 매개변수 index의 값을 비교하여

값이 같을 때 current_node를 반환

현재index와 매개변수 index의 값이 다를 경우

노드를 또 한 칸 이동하면서 현재index의 값을 1 증가시킴

위의 과정을 현재 노드(current_node)가 None이 될 때까지 반복함

한 칸 씩 이동하면서 현재index와 매개변수 index를 비교했을 때 결국 현재index와 매개변수 index가 같은 값을 못찾았다면 "None!!"이라는 문자열을 출력함

   def get_node(self, index):
        current_index = 0
        current_node = self.head
        while current_node is not None:
            if current_index == index:
                return current_node
            current_node = current_node.next
            current_index += 1
        return "None!!"

---

[Linked List에서 index번째 원소를 추가하기]

현재 노드의 다음 노드를 새로운 노드와 연결

새로운 노드의 다음 노드를 이전에 저장해놓은 노드에 연결

    def add_node(self, index, value):
        new_node = Node(value)
        # index-1 때문에 예외처리를 해줘야함
        if index == 0:
            new_node.next = self.head
            self.head = new_node  # Linked List의 맨 앞에 새 노드가 들어가야 함
            return
            
        # index-1:
        # index 위치에 노드를 추가하고 싶은거니까 바로 이전 노드에 이어붙여야함
        node = self.get_node(index-1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

 

 

 

[내가 만든 add_node 함수]

index-1인 이유: index 위치에 노드를 추가하고 싶은거니까 바로 이전 노드에 새 노드를 이어붙여야함

current_index가 index-1과 같아질 때 까지 current_node에 다음 노드를 저장하고 current_index를 1 증가시킴

index-1위치에 있는 노드의 다음 노드를 next_node에 저장하고

index 위치에 새노드를 만들어 새 노드의 다음노드에 next_node값을 저장

    def add_node(self, index, data):
        current_index = 0
        current_node = self.head
        while current_index < index - 1:
            current_node = current_node.next
            current_index += 1
        next_node = current_node.next
        current_node.next = Node(data)
        current_node.next.next = next_node

---

[Linked List에서 index번째 원소 제거]

index-1의 위치에 있는 노드의 다음 노드(next변수)에

index-1의 위치에 있는 노드의 다음 다음 노드를 저장

    def delete_node(self, index):
        # index-1에 대한 예외처리
        # 가장 맨 앞에 있는 노드를 그 다음에 있는 노드로 바꿈
        if index == 0:
            self.head = self.head.next
            return
        node = self.get_node(index - 1)
        node.next = node.next.next

 

 

 

[내가 만든 delete_node 함수]

index-1에 있는 노드의 다음 노드에다가

index+1에 있는 노드를 이어붙임

index-1과 index+1에 대해 예외처리도 해줌

    def get_node_length(self):
        count = 0
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
            count += 1
        return count

    def delete_node(self, index):
        # index가 노드의 맨 끝과 같다면 맨 끝의 이전 노드의 next 변수값을 없애버림
        if index == self.get_node_length():
            self.get_node(index-1).next = None
            return
        
        # index가 맨 첫번째 노드를 말한다면 두번째 노드를 Linked List의 head로 설정
        if index == 0:
            self.head = self.get_node(index+1)
            return
            
        node = self.get_node(index-1)
        node.next = self.get_node(index+1)

---

[전체 코드]

class Node:
    def __init__(self, data):
        self.data = data
        self.next = 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):
        if self.head is None:
            print("Node is None")
            return

        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next

    def get_node(self, index):
        current_index = 0
        current_node = self.head
        while current_index < index:
            current_node = current_node.next
            current_index += 1
        return current_node

    def add_node(self, index, value):
        new_node = Node(value)
        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 get_node_length(self):
        count = 0
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
            count += 1
        return count

    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