[자료구조] 링크드리스트 파이썬으로 구현

처음에 링크드리스트에 대한 개념이 잡히지 않아 이해하기가 힘들었다. 하지만 프로그래밍을하며 메모리를 사용하는 방법에 대해 어느 순간 감이 왔고 링크드리스트에 대한 이해가 완벽하진 않지만 예전보다는 많이 되었다.

 

배열은 순차적으로 메모리의 공간을 사용한다. 아래의 그림처럼 4개 짜리의 배열을 선언 후 각각에 값을 저장하여 순차적으로 데이터를 한 공간에 나열한다. 이렇게 하면 장점은 빠르게 원하는 index에 맞는 데이터를 찾을 수 있다. 학창시절에 새로운 학교에 입학 했을 때 2학년 10반을 찾으려고 한다면 보통 어떻게 했을까? 나는 계단을 오른 후 2학년 1반을 찾아 그 길로 계속 가면 10반이 나왔다. 1반에서 부터 10반이 한 층에 순차적으로 놓여있으면 반을 찾기가 쉽다. 

출처: https://dasima.xyz/javascript-array/

 

하지만 배열의 단점은 데이터를 삭제, 추가 할 경우 새로운 배열을 선언해야하고 항상 최대 길이를 지정해야한다. 데이터가 얼마나 많을지 예측이 불가능하므로 최대길이를 지정하는 것은 유연하지 않다고 생각이 든다.

 

링크드리스트는 이러한 배열의 단점을 보완하고자 다음 데이터가 있는 주소를 함께 저장한다. 2학년 10반을 찾았다면 그 교실에 다음 11반은 몇층 어디에 있는지 표시가 되어있다는 뜻이다. 이렇게 데이터의 마지막까지 찾을 수 있도록 도와준다.

출처: https://freestrokes.tistory.com/84

 

링크드 리스트를 사용하는 이유는 데이터의 추가와 삭제 시 배열을 다시 지정하지 않고 최대길이를 신경 쓸 필요없다. 메모리에 공간만 있으면 어디든지 데이터를 저장하고 주소만 이전 데이터에 넣어놓으면 된다. 대신 순차적으로 일직선으로 위치한 반을 찾는 것 보다는 여기저기 다니면서 반을 찾기 때문에 당연히 속도는 느려질 수 있다. 유연함을 갖으면 속도는 느려진다... 

 

링크드 리스트를 코드로 구현해보자. 

# 노드 정의
class Node:
  def __init__(self, data, next=None):
    self.data = data
    self.next = next


class NodeMgmt:
  def __init__(self, data):
    # 링크드리스트의 첫번째에 data를 저장
    self.head = Node(data)

  #링크드 리스트 마지막에 데이터를 넣는 메소드
  def add(self, data):
    # 첫번째 노드에 데이터가 없다면 추가하는 데이터가 첫번째가 된다.
    if self.head == "":
      self.head = Node(data)
    else:
      # 첫번째 노드를 node 변수에 담아주고
      node = self.head
      # node의 마지막을 찾기 위해 next가 False가 나올때까지 루프를 돈다.
      while node.next:
        node = node.next
      # False가 되면서 루프를 나오게 되면 마지막 노드라는 것이고 그 노드의 next에 추가하려는 데이터를 넣는다.
      node.next = Node(data)

  def desc(self):
    # 여기도 마찬가지로 node가 False가 되는 것이 마지막 노드이기 때문에 루프를 돌며 모든 노드를 출력한다.
    node = self.head
    while node:
      print(node.data)
      node = node.next
  
  def delete(self, data):
    if self.head == "":
      print("해당 값을 갖는 노드가 없습니다.")
      return
      # 첫번째 값을 지우려면 먼저 처음 노드를 지우고 head.next를 head에 저장하면 첫번째가 되는 것이다.
    if self.head.data == data:
      temp = self.head
      self.head = self.head.next
      del temp
    else:
      # 특정 node를 삭제하기 위해서 조건에 맞는 data를 루프를 돌며 찾는다.
      node = self.head
      while node.next:
        # 찾으면 그 노드는 temp로 빼서 지우고 다음 노드를 삭제 노드의 위치에 저장한다.
        if node.next.data == data:
          temp = node.next
          node.next = node.next.next
          del temp
          return
        else:
          node = node.next

출력 결과

# 먼저 0을 데이터로 넣고 1~10까지 데이터를 추가해보자.
linkedlist = NodeMgmt(0)

for data in range(1, 10):
  linkedlist.add(data)

# 이후 3을 제거
linkedlist.delete(3)
linkedlist.desc()

#출력 결과
0
1
2
3
4
5
6
7
8
9

배열은 생성하기 쉽지만 링크드리스는 조금 복잡하다.