[자료구조] Linked List- Python으로 구현하기

List 는 순서를 가지고 원소들을 저장하는 자료구조이다. 

List는 Array List, Linked List두 가지로 구현할 수 있다. 

 

✅ Array List

Array List는 Static Array (정적배열)과 Dynamic Array (동적배열)이 존재하는데,

Python에서는 list 자료형을 통해 dynamic array을 이미 잘 구현해 두었기 때문에 직접 구현할 필요가 없다. 

 

List의 Operation(연산)들과 시간복잡도는 다음과 같다. 

	Static array	Dynamic array
access / update	O(1)	O(1)
insert_back	O(1)	amortized O(1)
delete_back	O(1)	O(1)
insert_at	O(1)	O(1)
delete_at	O(1)	O(1)

 

 

✅ Linked List

Linked List는 Node 라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조이다. 

메모리가 물리적으로 불연속적이지만, 각 노드에 다음 노드의 메모리 주소값을 가지고 있기 때문에 논리적인 연속성을 가지고 있다. 

 

먼저 노드 class를 선언하고, LinkedList class를 선언하면서 핵심적인 operation을 구현하는 형식으로 구현했다. 

 

코드는 다음과 같다. 

 

class Node(object):
    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedList(object):
    def __init__(self):
        self.head = None

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
        else:
            current= self.head
            while(current.next):
                current = current.next    
            current.next = new_node
    # 인덱스로 해당 인덱스의 value를 가져오는 get 
    def get(self,idx):
        current =self.head
        for _ in range (idx):
            current =current.next
        return current.value
    
    # 해당하는 index에 삽입하는 insert_at()
    def insert_at(self, idx, value):
        new_node = Node(value)
        if idx == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            for _ in range(idx-1): 
                current = current.next #current를 idx 바로 전 노드로 이동 
            new_node.next = current.next #원래 idx에 있던 노드의 주소를 new_node.next에 저장
            current.next = new_node #idx-1 노드의 next에 new_node 저장 
    
    def remove_at(self, idx):
        current= self.head
        if idx == 0:
            self.head = current.next
        for _ in range(idx - 1):
            current = current.next
        current.next = current.next.next
        #파이썬에서는 아무도 참조하지 않는 노드를 가비지컬렉터가 자동으로 삭제해주기 때문에 별도의 노드 삭제코드는 필요 없다.
    def print(self):
        current = self.head
        while(current):
            print(current.value, end="")
            current = current.next    
            if current:
                print("->", end="")
        print()
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)
ll.append(5)
ll.insert_at(3,100)
print(ll.get(3))
ll.print()

ll.remove_at(4)

ll.print()

실행시 print 값은 다음과 같다 

 

이 외에도 각 노드가 이전 노드의 주소값을 가지고 있기에 양방향으로 접근이 가능한 doubly linked list도 존재한다. 

 

✅ Doubly Linked List 예시문제 

https://leetcode.com/problems/design-browser-history/

Design Browser History - LeetCode

 - 브라우저 히스토리( 방문, 이전페이지, 다음페이지 )구현하기 

class ListNode(object):
  def __init__(self, val=0, prev=None, next= None):
    self.val=val
    self.next=next
    self.prev=prev

class BrowserHistory(object):
  def __init__(self,homepage):
    self.head=self.current=ListNode(val=homepage)
  def visit(self,url):
    self.current.next=ListNode(val=url,prev=self.current)
    self.current=self.current.next
    return None
  def back(self,steps):
    while steps>0 and self.current.prev != None:
      steps -=1
      self.current=self.current.prev
    return self.current.val
  def forword(self,steps):
    while steps>0 and self.current.next != None:
      steps -=1 
      self.current=self.current.next
    return self.current.val

 

위에서 self.head나 self.tail을 선언할 때에 주의할 점이 있는데 

 

class BrowserHistory(object):
  def __init__(self,homepage):
    self.head=self.current=ListNode(val=homepage)	#1방법 
    
    self.head=ListNode(val=homepage)	#2방법 -> 틀린방법
    self.current=ListNode(val=homepage)
    self.tail= ListNode(val=homepage)

1방법처럼 해야 head와 current가 같은 Node를 바라보게 된다. 

2 방법처럼 하면 잘 돌아갈 듯 하지만 각각 다른 노드를 참조하고 있기 때문에 이후 오류가 발생한다.