Linked List 총정리

LinkedList란?

: 리스트와 달리 원소를 메모리에 저장하는 방식이 다른 선형 자료구조

 

개인적으로 Linked List는 꼬치와 비슷하다고 생각하는데요,

꼬치에 있는 각 재료들 = 원소들은 '노드'라고 불리고,  이 노드는 값을 지니고 있는 '데이터'와

다음 노드의 참조값을 가지고 있는 'Next'로 분류됩니다

 

출처: 크래프트하인즈

 

빈 막대기에 재료를 끼운다고 가정하면, 처음으로 끼우는 재료를 Head라고 부르는데요

우리가 꼬치에 재료를 다 끼우면 꼬치를 다 만들었다고 하죠? 마찬가지로 Linked List에서는 재료를 다 끼우고 나면 None을 반환합니다

 

https://realpython.com/linked-lists-python/#understanding-linked-lists

 

그러면 코드상에서 이러한 개념들이 어떻게 나타내질 수 있는지 봅시다

def __init__(self, nodes=None):
    self.head = None                              
    if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next
            
 (출처: Real Python)

위 코드를 해석해보자면,

1. 제일 먼저 꼬치의 첫 단계인 head를 지정해준다

2. 주어진 꼬치재료들(nodes)에 대해서 제일 첫 재료를 첫번째 node로 지정해준다.

3. 이 노드가 바로 head라고 알려준다 self.head = node

4. 꼬치의 재료를 하나하나 꺼낸다 --> for elem in nodes:

5. 앞에 head에 데이터가 있으니 그 다음 노드 node.next = Node(data=elem)에 for에서 꺼낸 재료를 끼워준다.

6. 다음 재료로 넘어가기 위해서 node를 그 다음 node.next로 바꿔준다.

 

 

---

그럼 이제 위의 개념을 가지고 여러 방법을 응용해보겠습니다 (자세한 내용은 realpython홈페이지 참조)

 

□ Linked List 나열하는 법

def __iter__(self):
    node = self.head
    while node is not None:
        yield node
        node = node.next

위 코드를 해석해봅시다!

1. 헤드에서 부터 노드를 시작해볼께    node = self.head

2. 꼬치끝인 None이 나오기 전까지 원소들을 뽑아볼꺼야 while node is not None

3. (여기서 yield는 return으로 생각하면 됩니다) 하나씩 뽑은걸 나열하자

4. 현재 노드는 이미 나열했으니,다음 노드는 node.next야

 

 

□ Linked List 제일 앞에 원소를 insert 하는 법

def add_first(self, node):
    node.next = self.head
    self.head = node

이 방법은 우리가 기존 꼬치를 올려서 새로운걸 끼워준다고 상상하면 되는데요

앞에서는 제일 처음에 self.head가 노드야라고 해줬지만, insert하는 원소가 head가 되어야 하기 때문에 node.next가 먼저 나오는데요

 

1. 여기서 헤드는 node.next 값이야

2. 새로 주어진 node값이 바로 node야

 

 

□ Linked List 제일 마지막에 원소를 insert 하는 법

def add_last(self, node):
    if self.head is None:
        self.head = node
        return
    for current_node in self:
        pass
    current_node.next = node

우선, 마지막 노드의 위치로 가려면 데이터 구조의 특성상 첫번째 원소 -> 끝자리까지 가서 원소를 insert해야겠죠?

마지막 자리까지 순회하는 구문이 for 문이고 원소의 마지막에 와서 for문이 끝났을 때, 끝난 current_node.next에 node값이 들어가게 되는 것이죠!

 

□ Linked List 중간에 원소를 insert 하는 법

 

떤 특정 데이터 값 다음에 새로운 노드를 넣고 싶을 때는 어떻게 할까요? 여기서도 마찬가지로 이 Linkedlist를 순회하고 특정 데이터와 같은 값이 되었을 때, new_node.next 침조값과 node.next의 참조값을 일치시켜주고 현재 노드의 next 참조값에 특정 값을 넣어주면 됩니다

 

def add_after(self, target_node_data, new_node):
    if self.head is None:
        raise Exception("List is empty")

    for node in self:
        if node.data == target_node_data:
            new_node.next = node.next
            node.next = new_node
            return

    raise Exception("Node with data '%s' not found" % target_node_data)