2주차 - 연결 리스트 (Linked List)

Python에서의 배열과 리스트

유형	설명
배열 (Array)	같은 Type의 자료끼리 묶은 모음 배열의 요소들은 메모리 상으로도 연속적으로 배치함
리스트 (List)	다른 Type의 자료끼리도 묶일 수 있음 리스트의 요소들은 메모리 상에서 연속적으로 배치될 필요가 없음

 기존에 있던 배열은 요소들을 저장하기 위해 메모리 공간을 연속적으로 사용한다고 했다. 이에 따라 이미 생성된 배열의 중간에 새로운 요소를 삽입하거나, 특정 요소를 삭제하기 위해서는 완전히 새로운 배열의 공간을 할당 받아 새로운 배열을 다시 만들어야 했다.

 

이러한 한계를 연결 리스트를 통해 해결할 수 있다.

 

연결 리스트(Linked List)

 연결 리스트란 위 처럼 '노드'를 연결시킨 자료구조다.

여기서 노드란 값을 저장하는 item과 다음 노드의 주소를 저장하는 link를 저장하는 자료구조다.

위 사진에서 볼 수 있듯이, 마지막 노드에 해당하는 포도 노드의 link는 null이 저장된다.

 

 연결 리스트는 앞서 언급한 '배열에서의 중간 요소 삽입, 삭제의 어려움'을 해결할 수 있다. 다음 노드의 주소를 가리키는 link의 값만 바꾸어주면 중간 요소의 삽입과 삭제를 간편히 해결할 수 있게 된다!

 

다만 연결 리스트는 값만 저장했던 배열과 달리, '노드'(값을 저장하는 item과 다음 노드의 주소를 저장하는 link를 저장하는 자료구조)를 연결했기 때문에 배열보다 메모리 공간을 2배 더 사용한다.

 

그리고 연결 리스트는 노드들이 메모리 내에 어디에 저장되어 있든지 link를 통해 찾을 수 있기 때문에 메모리 공간을 연속적으로 사용할 필요가 없다. 이로 인해 물리적으로 노드들이 저장된 메모리 공간들이 떨어져 있기 때문에 사용할 때 시간이 더 많이 소요될 수 있다.

 

연결 리스트의 장단점

리스트 (List)	설명
장점	요소를 추가할 때 노드 값만 바꾸면 됨 요소들을 저장하기 위해 메모리를 연속적으로 저장할 필요가 없음
단점	메모리를 많이 씀 연속적으로 저장되지 않았기 때문에 느림

연결 리스트는 위와 같은 장단점이 있다.

때문에 삽입, 삭제가 아주 빈번하고 그 규모가 클 경우에 Linked List를 사용하면 좋다.

 

실습: Linked List 구현하기

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


class LinkedList:
    def __init__(self):
        self.root = Node()
    
    def append(self, item):
        curNode = self.root
        newNode = Node(item)
        if(curNode.link == None):
            curNode.link = newNode
        else:
            while(curNode.link != None):
                curNode = curNode.link
            curNode.link = newNode

    def size(self):
        cnt = 0
        curNode = self.root
        while(curNode.link != None):
            curNode = curNode.link
            cnt += 1
        return cnt
    
    #insert
    def insert(self, index, item):
        curNode = self.root
        newNode = Node(item)
      
        for i in range(index):
            curNode = curNode.link
        _temp = curNode.link
        curNode.link = newNode
        newNode.link = _temp


    #search
    def search(self, item):
        curNode = self.root

        index = 0
        while (True):
            curNode = curNode.link
            if (curNode.item == item):
                break
            index += 1
        
        return index


    #delete
    def delete(self, item):
        curNode = preNode = self.root

        while (True):
            preNode = curNode
            curNode = curNode.link
            if (curNode.item == item):
                break
        preNode.link = curNode.link

    
    def pprint(self):
        #to print prettier, I programmed curNode as self.root.link
        curNode = self.root.link
        while(curNode.link != None):
            print(curNode.item, end=", ")
            curNode = curNode.link
        print(curNode.item)


fruits = LinkedList()
fruits.append('사과')
fruits.append('앵두')
fruits.append('배')
fruits.pprint()
fruits.size()
fruits.insert(2, '딸기')
fruits.pprint()
fruits.delete('배')
fruits.pprint()

#결과

사과, 앵두, 배
사과, 앵두, 딸기, 배
사과, 앵두, 딸기