[자료구조/Data Structure] 파이썬으로 연결 리스트(Linked List) 자료구조 알아보기

연결 리스트의 삽입 동작구조

연결 리스트의 삽입은 그림과 같이 동작한다.

 

• 연결 리스트를 초기화 하고 첫번째 데이터를 삽입시 head와 tail이 삽입된 node를 가리킨다.
• 1. 새로운 데이터를 삽입하면 tail이 가리키던 데이터의 next가 삽입되는 node를 가리킨다.
• 2. tail이 삽입된 node를 가리킨다.
• 1번과 2번을 계속 반복한다..

연결 리스트의 삭제 동작구조

연결 리스트의 삭제는 그림과 같이 동작한다.

 

• ① 임시 변수(temp)로 삭제할 node를 가리킨다.
• ② 삭제할 node의 바로 이전 node가 삭제할 node의 다음 node를 가르키게 한다.
• ③ temp가 가르키는 node를 메모리에서 삭제해준다.(파이썬에서는 del 키워드를 사용해서 삭제)

 

연결 리스트의 함수

• add(data) : data를 연결 리스트의 마지막에 삽입
• remove(data) : data를 가진 노드를 삭제 (단 head로부터 가까운 한개만 삭제된다.)

 

연결 리스트의 장점 

• 데이터를 동적으로 할당하기 때문에 공간 낭비가 적다.

연결 리스트의 단점

• node를 활용하고 node가 포인터 변수를 가지고 있기 때문에 공간을 추가로 차지한다.
• node를 다음으로 넘어가며 데이터를 삽입 및 삭제하기 때문에 데이터 검색 시간이 오래 걸린다.

 

파이썬을 활용한 연결 리스트 구현

class Node():

    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList():

    # '__'를 변수나 함수 앞에 붙여서 네이밍하면 private 효과
    def __init__(self):
        self.__head = None
        self.__tail = None

    def add(self, data):
        node = Node(data)
        if self.__head == None:
            self.__head = node
            self.__tail = node
        self.__tail.next = node
        self.__tail = node

    # 데이터 삭제
    # 단 데이터가 중복이여도 head에 가까운 값 하나만 지움
    def remove(self, data):
        if data == self.__head.data:
            tmp = self.__head
            self.__head = self.__head.next
            del tmp
        else:
            node = self.__head
            while node.next != None:
                if data == node.next.data:
                    tmp = node.next
                    node.next = node.next.next
                    del tmp
                    return
                else:
                    node = node.next
            print("해당 값이 존재하지 않습니다.")

    def printAll(self):
        node = self.__head
        while node != None:
            print(node.data)
            node = node.next