[자료구조] 연결리스트(Linked List), 파이썬 구현

안녕하세요

 

공부한 연결리스트를 정리해보려고 합니다.

 

먼저 배열과의 차이점을 알아보고 파이썬으로 구현해보도록 하겠습니다 😃

 

배열과의 주요한 차이점

연결리스트와 배열의 가장 큰 차이점 중 하나는 메모리에 저장되는 방식입니다.

배열이 메모리에서 저장되려면 필요한 공간을 연속적으로 할당 받아야 합니다.

정수 4개를 저장하는 배열은 다음과 같이 메모리에 저장됩니다.

 

 

32-bits 정수 자료형 이라면 4 개의 정수를 가지는 배열은 메모리에서 최소 16(4x4) 개의 메모리 슬롯이 필요합니다. 

여기서는 메모리 슬롯 한 칸이 한 개의 정수를 저장하는 공간에 대응된다고 가정하겠습니다.

즉, 정수가 32-bits 정수 자료형이면, 위 이미지에서 색칠된 메모리 슬롯 한 칸은 실제 메모리 슬롯 4칸과 같습니다.

 

만약에 어떤 이유에서 2 번, 5 번, 7 번, 9번 메모리 슬롯이 사용되고 있다면

배열은 10번 메모리 슬롯 이후에 연속적인 메모리 슬롯 공간에서만 저장될 수 있습니다.

 

빨강색으로 색칠된 부분은 이미 사용되고 있는 메모리 슬롯을 나타낸다

 

하지만 연결리스트는 배열과는 전혀 다르게 메모리에 저장됩니다.

2 --> 3 --> 5 --> 9 인 연결리스트 하나를 가정해보면,

연결리스트의 각 노드는 값(value) 뿐만 아니라 다음 노드를 가리키는 포인터를 가지고 있습니다.

 

그래서 연결리스트의 각 노드를 메모리에 저장하기 위해서는

값(여기서는 정수)을 저장할 공간과 더불어 포인터를 저장할 공간이 필요합니다.

 

그리고 중요한 점은 연결리스트는 포인터 덕분에 메모리안에서 연속된 공간에 저장될 필요가 없다는 것 입니다!

그림을 그려보면 다음과 같습니다.

 

주황색으로 색칠된 부분이 포인터가 저장된 공간이다

 

배열과는 다르게 배정받는 메모리 슬롯들이 산발적인 것을 알 수 있습니다.

 

정수 2 노드의 포인터는 정수 3 노드가 저장된 메모리의 주소를 가리킵니다. 

마지막 정수 9 노드의 포인터는 보통 null 값을 가르키며 연결리스트가 끝났다는 것을 암시하지만

처음 노드의 주소를 가리켜 사이클을 만들 수도 있습니다.

 

포인터 하나를 더 가져서 이전 node 를 가르키는 이중 연결리스트(Dobule Linked List) 도 있습니다. 

2 <--> 3 <--> 5 <--> 9

 

빨강색은 다음 노드를, 연두색은 이전 노드를 가르키는 포인터

 

 

이중 연결리스트의 경우 한 노드를 저장할 때

이전 노드를 가르키는 포인터와 더불어 다음 노드를 가르키는 포인터가 저장될 공간이 필요합니다.

 

연결리스트가 메모리에 저장되는 이런 방식 때문에 배열과는 다른 특징이 하나 드러나는데요. 

연결리스트에는 엄밀하게 배열의 인덱스 개념이 존재하지 않습니다.

 

배열은 메모리에 연속적으로 저장되기 때문에 배열에 저장된 값에 접근하는 비용이 매우 작습니다(O(1)).

인덱스와 (배열의 값 하나가 저장되는) 메모리 슬롯의 개수를 곱하면

해당 값이 저장 되어있는 메모리 슬롯으로 바로 이동할 수 있기 때문입니다.

 

하지만 연결리스트의 노드들은 메모리에 산발적으로 저장되어 있기 때문에 배열처럼 값에 접근할 수 없습니다.

이중 연결리스트 기준으로 p 번째 포지션에 있는 노드에 접근하기 위해서는

처음 노드나 마지막 노드에서 부터 순차적으로 포인터를 따라서 p 번째 노드에 접근해야 합니다.

그래서 특정 노드에 접근하는 시간복잡도가 O(p) 되게 됩니다.

 

연결리스트가 메모리에 저장되는 방식 때문에 배열 보다 더 높은 접근 비용을 가지는 것 입니다.

하지만 다른 기능들의 시간 복잡도는 배열보다 더 낮습니다.

코드로 구현해보면서 확인하면 알 수 있습니다.

 

추가적인 이야기는 이중 연결리스트를 구현하면더 더 해보겠습니다!

이중 연결리스트 구현

여러가지 방식으로 구현이 가능하겠지만 

연결리스트의 특징이 잘 드러나도록 구현을 해보려고 합니다.

 

먼저 기본적인 세팅을 합니다.

 

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


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

 

우선 노드를 정의하고 이중 연결리스트도 정의했습니다. 

연결리스트의 처음 노드는 head, 마지막 노드는 tail 이라고 합니다.

 

이중 연결리스트 클래스에 메소드를 하나씩 추가해볼게요.

 

먼저 특정 노드를 연결리스트에서 제거하는 메소드를 만듭니다.

삽입 메소드를 구현할 때 이 메소드를 사용할거라 먼저 만들어 줍니다.

 

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        
    # 특정 노드를 연결리스트에서 제거    
    def remove(self, node):
    # edge case: 노드가 head 거나 tail 일 경우
        if node == self.head:
        	self.head = self.head.next
        if node == self.tail:
        	self.tail = self.tail.prev
        
        self.removePointersOfNode(node)
    
    # remove 메소드의 helper function
    def removePointersOfNode(self, node):
    	if node.prev is not None:
        	node.prev.next = node.next
        if node.next is not None:
        	node.next.prev = node.prev

        node.prev = None
        node.next = None

    

 

remove 메소드의 엣지 케이스는 제거할 노드가 head 거나 tail 일 경우 입니다.

시간복잡도와 공간복잡도는 모두 O(1) 입니다.

 

이중 연결리스트를 구현할 때 주의해야 하는 점은 노드의 포인터를 조정하는 순서 입니다.

항상 순서를 생각해서 노드들의 포인터를 제대로 연결하는지 확인해야 합니다.

 

이제 특정 노드를 연결리스트에 삽입하는 메소드를 구현 해보겠습니다.

우선 삽입할 노드가 연결리스트에 이미 있는지 고려해야 합니다.

삽입할 노드가 연결리스트에 있다면 이 메소드는 사실상 노드의 위치를 바꾸는 기능으로도 볼 수 있습니다.

 

삽입 메소드는 두 개를 구현하겠습니다.

insertBefore 와 insertAfter 입니다.

먼저 insertBefore 를 구현해보면 다음과 같습니다.

 

# class DoublyLinkedList 계속

def insertBefore(self, node, nodeToInsert):
    # edge case: 연결 리스트가 하나의 노드로만 구성되어 있을 때 e.g. <-- 3 -->
    
    if nodeToInsert == self.head and nodeToInsert == self.tail:
	    return
        
    self.remove(nodeToInsert)

    nodeToInsert.prev = node.prev
    nodeToInsert.next = node

    # node 가 head 인 경우와 아닌 경우를 구분
    if node.prev is not None:
	    node.prev.next = nodeToInsert
    else:
    	self.head = nodeToInsert

    node.prev = nodeToInsert

 

insertBefore 메소드는 인자 node 앞으로 nodeToInsert 를 삽입하는 메소드 입니다.

 

엣지 케이스로 노드가 하나인 연결리스트인 경우를 고려해야 합니다.

 

nodeToInsert 를 인자로 remove 메소드를 호출하면 

nodeToInsert 가 기존에 연결리스트에 있었다면 연결리스트에서 제거 될 것이고

그렇지 않았다면 아무 일도 일어나지 않습니다.

 

remove 와 마찬가지로 포인터를 조정해줄 때 순서가 중요합니다.

시간복잡도와 공간복잡도 모두 O(1) 입니다.

 

insertAfter 는 insertBefore 와 거의 동일합니다. 

 

def insertAfter(self, node, nodeToInsert):
    if nodeToInsert == self.head and nodeToInsert == self.tail:
	    return

    self.remove(nodeToInsert)

    nodeToInsert.prev = node
    nodeToInsert.next = node.next

    if node.next is not None:
    	node.next.prev = nodeToInsert
    else:
    	self.tail = nodeToInsert

    node.next = nodeToInsert

 

이제 위의 메소드를 이용해서 setHead 메소드와 setTail 메소를 구현하면 됩니다.

 

def setHead(self, node):
# edge case: 연결리스트가 비어있을 때
    if self.head is None:
    	self.head = node
        self.tail = node
        return
    
    self.insertBefore(self.head, node)

def setTail(self, node):
	if self.tail is None:
		self.head = node
		self.tail = node
		return
    
    self.insertAfter(self.tail, node)
    	

 

시간복잡도와 공간복잡도 모두 O(1) 입니다.

 

이제 p 번째 위치에 노드를 직접 삽입하는 메소드를 위 메소드들을 이용해서 만들어 보겠습니다.

 

# position 에 node 를 삽입하는 메소드
def insertAtPosition(self, position, nodeToInsert):
    # head 의 position 은 1 로 정의
    if position == 1:
    	self.setHead(nodeToInsert)
        return
    
    node = self.head
    currentPosition = 1
    
    while node is not None and currentPosition != position:
    	node = node.next
        currentPosition += 1
    
    # currentPosition == position 조건으로 while 문을 탈출 했을 때와 아닐 때를 구분
    if node is not None:
       self.insertBefore(node, nodeToInsert)
    else:
       self.setTail(nodeToInsert)

        
    
    

 

worst 일 때 시간복잡도는 O(N) 입니다. 

삽입할 노드의 위치가 tail 과 가까울 경우 tail 부터 시작해서 접근할 수도 있지만 

어차피 상수배 이므로 head 부터 시작하는 경우만 고려할게요.

 

전체적인 코드는 다음과 같습니다.

 

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

		
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def setHead(self, node):
        if self.head is None:
			self.head = node
			self.tail = node
			return
            
        self.insertBefore(self.head, node)
        
    def setTail(self, node):
        if self.tail is None:
			self.head = node
			self.tail = node
			return
            
        self.insertAfter(self.tail, node)
    
    def insertBefore(self, node, nodeToInsert):
    	if nodeToInsert == self.head and nodeToInsert == self.tail:
			return
		self.remove(nodeToInsert)
		nodeToInsert.prev = node.prev
		nodeToInsert.next = node
        
        # case where node is head or not
        if node.prev is not None:
           node.prev.next = nodeToInsert
        else:
        	self.head = nodeToInsert
            
        node.prev = nodeToInsert
		
    def insertAfter(self, node, nodeToInsert):
        if nodeToInsert == self.head and nodeToInsert == self.tail:
			return
		self.remove(nodeToInsert)
		nodeToInsert.prev = node
		nodeToInsert.next = node.next
        
        if node.next is not None:
        	node.next.prev = nodeToInsert
        else:
        	self.tail = nodeToInsert
        
        node.next = nodeToInsert
        
    def insertAtPosition(self, position, nodeToInsert):
	    if position == 1:
	        self.setHead(nodeToInsert)
	        return

	    node = self.head
	    currentPosition = 1

	    while node is not None and currentPosition != position:
		    node = node.next
		    currentPosition += 1

	    if node is not None:
		    self.insertBefore(node, nodeToInsert)
	    else:
		    self.setTail(nodeToInsert)

    def remove(self, node):
	    if node == self.head:
	        self.head = self.head.next
	    if node == self.tail:
	        self.tail = self.tail.prev

	    self.removePointersOfNode(node)
	
    def removePointersOfNode(self, node):
        if node.prev is not None:
            node.prev.next = node.next
        if node.next is not None:
            node.next.prev = node.prev

        node.prev = None
        node.next = None

 

연결리스트를 배열과의 차이점을 중심으로 간단하게 살펴보고 구현도 해보았습니다.

 

아직 연결리스트를 실제로 활용해본적이 없는데 어느 상황에서 쓰고 어떻게 쓰는지 궁금하네요😃