[자료구조] 2. 링크드 노드 개념 및 예시코드 (feat. codestates, self_tutorial)

 

 

 

 

 

안녕하십니까 다제입니다. 

 

자료구조에 대해서 공부를 진행하고 있습니다. 

 

오늘은 자료구조의 핵심 개념인 링크드 노드(연결리스트)의 정의, 작동원리, 예시코드까지 함께 살펴보도록 하겠습니다. 

 

또한, 본 포스팅에서 사용된 예시코드 링크도 함께 공유 드리오니 꼭! 코드박스 단위로 실행해보시면 공부를 진행하시면 좋겠습니다. 

 

그럼 바로 진행하겠습니다. 

 

 

---

 

 

1. 개발배경 

도대체 링크드 노드는 갑자기 어디서 나와서 우리를 이렇게 괴롭히는 걸까요?

처음듣는 개념이다보니 멘탈이... 와르르 

 

우리는 지금까지 Python의 List, dict, tuple, DataFrame 형태로 데이터를 다루었습니다. 

그런데, 각각의 자료형에서 모든 데이터가 필요하지 않는 상황이 발생되었습니다. 처음에는 모든 데이터를 불러와서 사용을 하였지만 점점 필요 없는 정보들이 눈에 거슬리게 된거죠. 

 

아! 내가 필요한 정보만 연결하면 좋겠다! 라는 생각을 하게 되면서 각각에 노드에 필요한 정보를 담고 해당 노드를 연결하는 방식인 링크드 노드가 1955~1956년경 개발되게 됩니다. 이는 나중에 2008년~2009년 개발된 블록체인의 체인의 기본 개념으로 사용되게 됩니다. 

 

 

---

 

 

2. 개념

노드라는 단위에 데이터를 저장하고 데이터가 저장된 노드들을 순서대로 연결하여 만든 자료구조 입니다.  

 

정의가 정확히 와닿지 않으실거 같아서 그림을 준비하였습니다. 

아래에 4개의 노드가 있으며, 각각의 노드는 n1, n2 n3, n4 라는 이름을 가지고 있습니다. 

 

또한, 1개의 노드는 2개의 칸으로 구성되어 있습니다. 

 

노드의 왼쪽 칸에는 데이터를 넣고

노드의 오른쪽 칸에는 현재 노드 다음에 왔으면 좋겠다는 노드의 이름을 넣어준다고 생각하시면 됩니다.  

즉, 각 박스들을 순서대로 연결시켜주었기 때문에 이를 링크드 노드(연결 리스트)라고 이야기를 합니다. 

 

여기서에서 주의해야할 점은

각각의 노드들이 순서대로 나열되어 있으나,

실제 메모리 상에서는 여기 저기 흩어져 있으니 이점 주의하여 주셔야 합니다. 

출처 이미지 링크 참조

 

 

 

---

 

 

3. Linked Node 구성

직접 제작한 이미지 : 출처를 밝히고 사용하셔도 됩니다.

 

 

---

 

 

4. 작동원리 & 예시코드 

자~ 그렇다면 이를 코드로 어떻게 구현해야 할까요?

# n1과 n2 연결하기 
n1.next = n2 

#n1.next는 n2의 레퍼런스라고 합니다. 

위와 같이 .next를 가지고 레퍼런스를 설정하면 순서대로 찾아갈 수 있습니다. 

여기서 n1이 시작 노드가 되지요? 이를 head라고 합니다. 

 

그럼 이제부터 각각의 노드를 연결해주는 클래스를 만들어 보도록 하겠습니다. 

class Node:
"""링크드 리스트의 노드 클래스정보"""
	def __init__(self, data):
    	self.data = data # 노드의 저장공간에 들어갈 데이터 생성
        self.next = None 
        # 처음 head 노드가 만들어줄때는 아직 어디로 연결을 해주어야할지 모르기 때문에
        # 이를 None으로 설정하여 잠시 비워두도록 하겠습니다. 
        # 즉, 다음 노드에 대한 레퍼런스가 됩니다. 
        
# 아래 숫자를 가지고 노드들을 생성해보겠습니다. 
# [9, 10, 11, 12, 13]
head_node = Node(9) #첫번째 생성된 노드는 head_node라고 함 
node_1 = Node(10)
node_2 = Node(11)
node_3 = Node(12)
tail_node = Node(13) #마지막 생성된 노드는 tail_node라고 함 

이렇게 생성된 노드들은 생성만 되었을뿐 아직 연결이 이루어지지 않았음을 기억하여 주셔야합니다. 

왜냐하면 우리는 self.next = None으로 설정해두었기 때문입니다. 

 

각각의 노드를 연결하고, 출력까지 진행을 해보겠습니다. 

# 노드들을 연결
head_node.next = node_1
node_1.next = node_2
node_2.next = node_3
node_3.next = tail_node
# tail_node는 마지막 노드이므로 다음 노드에 대한 정보는 None으로 비워두겠습니다. 
# None은 별도로 설정해주지 않아도 클래스에 있기 때문에 추가적인 코드를 적지 않는 것입니다. 


#노드를 순서대로 출력
iterator = head_node

while iterator is not None:
  print(iterator.data)
  iterator = iterator.next

# tail_node.next는 None이므로 종료가 되고 9, 10, 11, 13이 출력이 됩니다. 

지금까지 Node 라는 class를 만들고 각각의 노드를 연결하는 것까지 해보았습니다. 

이제는 Linked_List class를 만들어서 추가적인 함수들을 구현해보겠습니다. 

 

 

---

 

 

그러나, 해당 코드는 정말 간단한 예시코드입니다.

이제는 진짜 링크드 노드 클래스를 만들어 보도록 하겠습니다. 

class LinkedList:
	# 링크드 리스트 클래스
	def __init__(self):
        self.head = None
        self.tail = None

	# 링크드 리스트 추가 연산 메소드     
    def append(self, data):
        new_node = Node(data)
        
        # append를 할때 경우의 수는 2가지가 있다
        # 1. head가 없을때
        # -. head가 없을 때는 첫번째로 들어노는 노드가 head이면서 tail이 된다. 
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        
        else:
        # 2. head가 있을때 
    	# -. 이곳에는 2가지 일이 일어나야합니다. 
        # 2-1). tail_node에 new_node를 추가해야하고
            self.tail.next = new_node
        # 2-2). 새롭게 들어온 new_node를 tail_node로 변경해야한다. 
            self.tail = new_node

# 새로운 링크드 리스트 생성 
lk = LinkedList()

# 링크드 리스트에 데이터 추가 
lk.append(2)
lk.append(3)
lk.append(4)
lk.append(5)
lk.append(7)
lk.append(11)

 

자! 이렇게 LinkedList class를 만들어 보았습니다. 

 

잘 Linked 되어 있는지 확인 한번 해볼까요?

print(lk.head.data)
print(lk.head.next.data)
print(lk.head.next.next.data)

출력값은 2,3,4 로 정상적으로 출력되는 것을 볼 수 있습니다. 

반복문을 통해서도 출력을 진행해볼까요?

# 위에서 사용한 코드 중 head_node만 lk.head로 변경해주면 됩니다. 
iterator = lk.head

while iterator is not None:
  print(iterator.data)
  iterator = iterator.next
  
# 출력값 : 2,3,4,5,7,11

위 코드를 class 내부에 넣어주도록 하겠습니다. 

아래처럼 def find_node_at(self, index)를 추가하여 줍니다. 

class LinkedList:
	# 링크드 리스트 클래스
	def __init__(self):
        self.head = None
        self.tail = None


    def find_node_at(self, index):
    """링크드 리스트 접근 연산 메소드"""
        iterator = self.head

        for _ in range(index):
            iterator = iterator.next

        return iterator 


	# 링크드 리스트 추가 연산 메소드     
    def append(self, data):
        new_node = Node(data)

 

이제 아래 코드를 실행하여 정상적으로 코드가 작동하는지에 대해서 알아보도록 하겠습니다. 

print(lk.find_node_at(3).data)
# 출력값 : 5 가 정상적으로 출력됩니다. 

 

위에 문제는 연결리스트는 인덱싱이 불가능합니다. 

Python의 list(동적배열)처럼 특정 인덱스 값을 입력하여 해당하는 데이터에 접근이 불가능합니다. 

 

오직, next, next, next하여 순차적으로만 접근이 가능합니다. 

즉, 인덱스 n에 있는 노드에 접근하려면 head로부터 n번 이동을 해야합니다. 

 

만약 데이터가 엄청 많다면 링크드 노드(연결리스트)는 시각복잡도가 엄청 증가를 하겠죠!

그럼 중간에 있는 노드를 찾아갈때는 어떻게 해야하지? 차차 알아보도록 하겠습니다. 

지금까지는 노드를 추가하는 방법에 대해서 알아보았습니다. 

만약 맨 뒷쪽에 추가하지 않고, 노드와 노드 중간에 삽입을 하고 싶을 때는 어떻게 해야할까요?

 

insert_node func을 만들어야겠죠?

노드와 노드에 삽입을 할 때는 두 가지 경우가 있습니다. 

1) head 앞에 삽일할 경우, 2) 노드와 노드 사이에 삽입을 할 경우 가 있습니다. 

 

그런데 노드를 접근 할 때는 next, next를 해야 접근할 수 있다는 건 미리 말씀을 드렸죠?

그렇다면 매번 next를 쓰셔 접근을 한다면 10000번째 있는 노드를 접근을 하려면 얼마나 많은 next를 써야할까요?

이건 매우 비효율적이죠 그러니 함수를 만들어야하겠죠?

 

그럼 insert를 하려면 find_node_func와 insert_func을 만들어야 합니다. 

바로 코드로 만들어보겠습니다. 

  def search_node(self, index):
    """링크드 리스트 접근 연산 메소드"""
    iterator = self.head
    for _ in range(index):
        iterator = iterator.next
    return iterator 

 

입력받은 index가 for문을 돌면서 각각의 노드를 찾아갑니다. 

 

  def insert_after(self, previous_node, data):
    """노드 삽입 연산 메소드"""
    new_node = Node(data)

    # tail_node 뒤에 삽입하는 경우
    if previous_node is self.tail:
      self.tail.next = new_node
      self.tail = new_node

    else:
    # 노드와 노드 사이에 삽입하는 경우
      new_node.next = previous_node.next
      previous_node.next = new_node

insert_after를 실행하기 위해 self, 이전 노드, 그리고 입력하고자 하는 데이터를 3개를 받아와야 합니다. 

먼저 입력 받은 데이터를 new_node라는 변수에 저장을 하고

previous_node가 tail_node라면 tail_node를 tail_node.next로 설정해야 합니다. 

그리고 self.tail에 new_node라는 변수를 저장해줘야 합니다. 그렇다면 삽입처리가 완료됩니다. 

 

  def prepend(self, data):
      """링크드 리스트의 가장 앞에 데이터 삽입"""
      
      new_node = Node(data)
      '''
      # 만약 해당 코드를 사용하지 않는다면 
      # AttributeError: 'int' object has no attribute 'next' 
      # UnboundLocalError: local variable 'new_node' referenced before assignment 
      # 위와 같은 에러를 만날 수 있는데요
      # 그 이유는 아래와 같습니다. 
      # You are appending int elements (instead of Nodes) to the list as your append method is designed for Nodes (as next_element) but you are passing ints.
      # 출처 : https://stackoverflow.com/questions/63301445/linked-list-error-int-object-has-no-attribute-next
      '''
      
      if self.head is None:
          self.head = new_node
          self.tail = new_node

      else:
          new_node.next = self.head
      
      self.head = new_node

이런 질문이 또 생길 수 있습니다.

만약, head 앞에 삽입을 하고 싶은 경우는 어떻게 해야 할까요?

 

이 경우에도 2가지를 살펴보아야 합니다. 

self.head가 있는 경우와 self.head가 없는 경우입니다. 

 

self.head가 없다면 새로 입력 받은 데이터를 지정해주면 됩니다. 

만약 self.head가 있다면 self.head를 self.head.next로 지정하여 주고, self.head에는 새롭게 입력 받은 데이터를 지정하여 주기만 하면 됩니다. 

 

이제, 대망의 마지막 입니다. 

그렇다면 삭제는 어떻게 진행해야할까요?

  def delet_after(self, previous_node):
    """링크드 리스트 삭제 연산"""

    # 삭제를 할때는 어떤 값을 삭제를 하였는지 알아야하기 때문에 
    # 해당 data를 return하는 것이 관습이라고 합니다. 
    # 이에, 해당 데이터를 return 하기 위해 data라고 변수를 설정하고 아래에서 리턴하겠습니다. 
    data = previous_node.next.data

    '''
    tail_node를 삭제하는 경우는 
    tail_node의 previous_node가 node을 가르키게만 하면 된다. 
    이제 previous_node가 tail_node가 되도록 지정해주기만 하면 됩니다. 
    '''
    '''  
    2,3,5,7의 링크드 노드가 있다고 해보겠습니다. 
    이때 5를 삭제한다고 하면 3을 7에게 연결만 해주면 된다.
    코드로 살펴보면 아래와 같습니다.
    '''
    if previous_node.next is self.tail:
      previous_node.next = None
      tail_node = previous_node
    else:
      previous_node.next = previous_node.next.next
    
    return data 

여기도 경우에 수가 두가지로 나뉩니다. 

삭제하려고 하는 경우가 tail_node일때, tail_node가 아닐때 입니다. 

tail_node라면 tail_node의 previous_node.next를 None으로 지정해줍니다. 

그렇다고 해서 self.tail의 데이터 값이 사라지는 것은 아니고 단순히 연결만 종료가 됩니다. 

 

또한, tail_node가 아니라면 previous_node의 previous_node.next.next 노드에 연결만해주면 중간에 값은 연결이 끊어지게 되기 때문에 바로 삭제가 되는 것을 알 수 있습니다. 

 

혹시 수업시간에 했던 코드로 위 내용을 어떻게 구현해야할까? 

고민하시는 분들을 위해 튜토리얼을 만들어서 깃허브에 공유해놓았습니다. 

맨마지막쪽으로 보시면 확인하실 수 있습니다. → 튜토리얼링크

 

 

오늘도 방문해주셔서 감사드리고, 궁금하신 사항이 댓글로 연락 부탁드립니다. 

다음 보스팅에서는 스택과 큐에 대해서 포스팅하도록 하겠습니다. 

 

 

감사합니다.