[Python 자료구조] 연결리스트_implemented Linked List@_탐색, 순회, 추가 및 삭제

강력한 스크립트 언어 파이썬 입니다!

Powerful Linked List Structure on Python

  저번에는 파이썬을 사용해서 트리 자료구조를 구현해보았습니다. 이번 시간에는 파이썬을 이용해서 연결 리스트를 구현해보도록 하겠습니다. 사실 우리가 사용하는 배열이나 선형 자료구조들은 이러한 개념을 바탕으로 설계되었으니, 어쩌면 우리는 사용하고 있었던 것입니다. 왜냐면 아래 그림을 보면 알 수 있습니다!!

연결리스트 추상도

연결 리스트는 하나의 데이터를 노드라고 지칭하고, 노드가 다음 노드를 가리키는 선은 노드 간 간선이라고 지칭합니다. 선의 형태를 띤다 하여 선형 자료구조라고 부르며, 가장 이해하기 쉬운 자료구조이며 삽입과 삭제는 최선, 최악의 경우 모두 O(1) 안으로 이루어지며, 탐색의 경우에는 O(n)이 걸리는 자료구조입니다. 파이썬에서는 그냥 리스트를 사용하면 그게 링크드 리스트나 다름없지만, 파이썬에서 링크드 리스트를 구현해서 사용해보도록 하겠습니다!! 사용하는 것과 구현해보는 건 차이가 크니까요.

 

Implemented Node

 

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

 

우선 연결리스트의 개별 데이터가 될 노드를 선언해줍니다. 내부에는 값과 다음 노드를 가리키는 변수가 포함되어있습니다. 초깃값으로 None을 준 이유는 클래스 생성 시에 아무런 값도 넣어주지 않고 선언하고 싶을 때 None을 초깃값으로 설정합니다.

 

Implemented LinkedList

  코드가 비교적 어려운 편이 아니기 때문에 연결 리스트의 전체 코드를 넣어서 설명하도록 하겠습니다.

 

 

class LinkedList:
    def __init__(self, head = None):
        self.head = head
        self.size = 0

    def push(self, value):
        newNode = Node(value)
        if self.head is None:
            self.head = newNode
            return
        else:
            temp = self.head
            while temp.link is not None:
                temp = temp.link
            temp.link = newNode
            newNode.link = None
            return
    
    def pop(self, value):
        temp = self.head
        temp2 = self.head
        if temp.value == value:
            self.head = temp.link
            del temp
            return
        else:
            while temp is not None:
                if temp.value == value:
                    break
                prev = temp
                temp = temp.link
            if temp is None: return
            prev.link = temp.link
            del temp
            return
    
    def show(self):
        temp = self.head
        while temp is not None:
            print(f"{temp.value}")
            temp = temp.link

    def retHeadVal(self):
        return self.head.value

 

size라는 클래스 속성은 여러분이 연결리스트를 구현하면서 사이즈를 확인하고 싶을 때 사용하시라고 만든 것이며, 제가 구현한 클래스 내부에서 사용되는 속성은 아니니 무시해도 상관은 없습니다. head변수는 연결 리스트의 맨 앞부분을 가리키는 변수입니다. push함수를 보게 되면 새로운 인자를 하나 받습니다.

 

newNode = Node(value) # 새로운 노드 생성
if self.head is None:
	self.head = newNode # head가 None일 때 head를 새로운 노드로 대입
    return
        
else:
	temp = self.head # 임시 노드 변수를 생성(self.head의 복삿값)
    while temp.link is not None: # 노드의 다음 노드가 없을 때 까지 찾음
    	temp = temp.link 
    temp.link = newNode # 순회노드의 다음 값으로 새로운 노드를 그 다음 노드로 지정
    newNode.link = None
    return

 

설명대로만 코드를 천천히 작성하시면 무슨 뜻인지 이해할 수 있습니다. 그렇다면 pop을 보도록 하겠습니다. 아무래도 삽입에 비해서 조금 더 어려운 형태인데요,

 

def pop(self, value):
        temp = self.head # head노드의 복삿값
        if temp.value == value:
            self.head = temp.link # head노드가 제거될 값과 같을 경우
            # head노드를 head노드의 다음 노드로 지정하고 삭제
            del temp
            return
        else:
            while temp is not None:
            # temp의 값과 제거될 키값이 같은 경우 중지
                if temp.value == value:
                    break
                prev = temp #temp노드의 이전노드
                temp = temp.link
            if temp is None: return #temp노드가 None이면 종료
            prev.link = temp.link # temp노드의 이전 노드가 temp노드의 다음 노드를 가리킴
            #그렇게 해야 연결이 중간에 있는 노드가 빠져도 연결이 되기 때문임
            del temp
            return

 

함수 내 주석문을 잘 따라가면서 코드를 작성하다 보면 무슨 코드인지 이해하실 수 있으리라고 생각합니다. 외에 순회해서 출력하는 show함수는 삽입과 삭제 로직에서 배운 경험을 통해 이해를 해보시기 바랍니다!!!

 

__Name__

 

if __name__ == "__main__":
    ll = LinkedList()
    ll.push(1)
    ll.push(2)
    ll.push(3)
    ll.push(4)
    ll.push(5)
    ll.show()
    print("_---_")
    ll.pop(3)
    ll.pop(4)
    ll.show()
    print("_---_")
    print(ll.retHeadVal())

 

클래스들이 모두 준비되었으니, 한번 동작해보도록 하겠습니다. 값의 출력도 무리없이 진행되었으며, 모든 게 정상적으로 동작함을 알 수 있습니다. 만약 문제가 있는 분은 댓글로...ㅎㅎ

 

연결 리스트에 대해서 알아보았는데, 비교적 쉬운 자료구조라서 빨리 이해를 할 수 있지 않을까 그렇게 생각해봅니다. 

 

글 잘 읽으셨다면 공감 하트 부탁드립니다!!😍😍😍

 

댓글로 문의, 피드백, 질문 모두 받습니다!

 

감사합니다😘😘😘😘