Double Linked List

# Double Linked List

Double Linked List는 헤드노드와 테일노드를 가지고 있으며 next 포인터 뿐만아니라 이전 노드를 가리키는 prev 포인터를 가지고 있습니다. 헤드노드의 next포인터는 테일노드를 가리키고, 테일노드의 prev포인터는 헤드노드를 기리키는 형태입니다

Single Linked List에 비해 prev포인터를 위한 공간을 더 필요로 하기 때문에, 같은 성능인 경우 상대적으로 공간을 덜 차지하는 Single Linked List를 사용하는 것이 용이하겠죠

하지만, 공간이 더 필요함에도 불구하고 Double Linked List를 사용하는 이유가 있습니다.

데이터 추가 기능을 구현할 때 double linked list의 이점을 볼 수 있습니다.

single linked list에서는 노드를 추가할 위치(마지막노드)를 찾기 위해서는 데이터갯수 O(N)만큼의 시간복잡도가 발생했지만, double linked list에서는 노드 추가할 위치(마지막노드)를 테일노드를 통해 한번에 접근할 수 있으므로 O(1)의 시간복잡도가 발생합니다

그럼 기능구현과 코드를 같이 살펴보겠습니다.

 

 

# 코드 구현 (python)

우선 노드 생성 클래스를 만들어 줍니다.

class Node:
    # 노드의 기본 구성(데이터, prev pointer, next point)
    def __init__(self, data, prev_node, next_node):
        self.data = data
        self.prev_node = prev_node
        self.next_node = next_node
    # 노드의 데이터
    def get_data(self):
        return self.data
    # 이전 노드
    def get_prev(self):
        return self.prev_node
    # 다음 노드
    def get_next(self):
        return self.next_node
    # 이전 노드 지정(prev pointer)
    def set_prev(self, new_prev):
        self.prev_node = new_prev
    # 다음 노드 지정(next pointer)
    def set_next(self, new_next):
        self.next_node = new_next

class DoubleLinkedList:
    def __init__(self):
        self.head = Node(None)  #dummy node
        self.tail = Node(None)
        self.size = 0
        self.head.set_next(self.tail)
        self.tail.set_prev(self.head)

 

 

[ add ] 

double linked list에서 추가 기능은 tail 앞에 새로운 노드가 추가됩니다. 그래서 우리는 새로운 노드에 대해 포인터만 바꿔주면 쉽게 구현할 수 있습니다.

def add(self, data):
    last = self.tail.get_prev()
    new_node = Node(data, last, self.tail)
    last.set_next(new_node)
    self.tail.set_prev(new_node)
    self.size += 1

    last = self.tail.get_prev()        : tail node의 이전 노드를 last라 설정
    new_node = Node(data, last, self.tail)    :입력받은 데이터(data)와 prev_node로 last를 가리키며 next_node로 tail을 가리키는 new_node 객체 생성

    last.set_next(new_node)    : last의 next_node로 new_node를 지정
    self.tail.set_prev(new_node)  :  tail의 prev_node로 new_node를 지정

 

 

[ insert ] 

double linked list에서 index를 통한 삽입 기능은 새로운 노드를 삽입하고자 하는 위치까지 head 혹은 tail 통해서 접근이 가능합니다. 삽입하고자하는 위치index가 전체 사이즈의 반보다 앞이면 head를 통해, 뒤면 tail을 통해 접근합니다.

그래서, 시간복잡도는 O(N/2)을 가집니다. (점근표기법에 따라 O(N)으로 표기)

삽입하고자하는 위치를 찾아 새로운 노드를 생성하고 이전노드와 다음노드의 연결을 새로운 노드로 바꿔줍니다.

def insert(self, idx, data):
    prev = Node(None)
    curr = Node(None)
    i = 0
    if (idx < self.size/2):   #index가 헤드에서 더 가까우면
        prev = self.head
        curr = self.head.get_next()
        i += 1
        while i < idx:
            prev = prev.get_next()
            curr = curr.get_next()
        new_node = Node(data, prev, curr)
        prev.set_next(new_node)
        curr.set_prev(new_node)
    else:   #index가 tail에서 가까우면
        curr = self.tail
        prev = self.tail.get_prev()
        i += 1
        while i < (self.size-idx):
            curr = curr.get_prev()
            prev = prev.get_prev()
        new_node = Node(data, prev, curr)
        prev.set_next(new_node)
        curr.set_prev(new_node)
    self.size += 1

def insert(self, idx, data):
    prev = Node(None)
    curr = Node(None)
    i = 0      : 노드 초기값 설정
    if (idx < self.size/2)
        prev = self.head       : 삽입할 자리 찾아가기위해 head에서 부터 시작(시작이 head라서 이전 노드가 없음)
        curr = self.head.get_next()    : head의 다음노드로 curr 설정
        i += 1
        while i < idx:       : 인덱스까지 뒤로 노드하나씩 넘어감
            prev = prev.get_next()
            curr = curr.get_next()
        new_node = Node(data, prev, curr)   : 인덱스에 도달하면 새로운 노드 생성

        prev.set_next(new_node)     : prev의 다음 노드를 new_node로 지정
        curr.set_prev(new_node)     : curr의 이전 노드를 new_node로 지정
    else:       : index가 tail에서 가까우면 else문 실행
        curr = self.tail    : 삽입할 자리 찾아가기위해 tail에서 부터 시작 (현재노드가 tail이라서 다음 노드는 없음)
        prev = self.tail.get_prev()   : 현재 노드 curr의 이전 노드
        i += 1
        while i < (self.size-idx):   : 인덱스까지 앞으로 하나씩 넘어감
            curr = curr.get_prev()     
            prev = prev.get_prev()
        new_node = Node(data, prev, curr)   : 인덱스에 도달하면 새로운 노드 생성
        prev.set_next(new_node)   : prev의 다음 노드를 new_node로 지정
        curr.set_prev(new_node)    : curr의 이전 노드를 new_node로 지정
    self.size += 1      : 새로운 노드 추가 됐으면 사이즈 늘림

 

[delete]

double linked list에서 추가 기능은 tail 앞에 새로운 노드가 삭제됩니다. 그래서 우리는 새로운 노드에 대해 포인터만 바꿔주면 쉽게 구현할 수 있습니다. 시간복잡도(O(1))

def delete(self, data):
    curr = self.tail.get_prev()
    (curr.get_prev()).set_next(self.tail)
    self.tail.set_prev(curr.get_prev())
    curr.set_prev(None)
    curr.set_next(None)
    self.size -= 1

    curr = self.tail.get_prev()    삭제하고자하는 노드를 curr로 설정
  

    (curr.get_prev()).set_next(self.tail)    curr이전 노드와 tail을 연결
    self.tail.set_prev(curr.get_prev())     
  

    curr.set_prev(None)     curr의 포인터 삭제
    curr.set_next(None)     curr의 포인터 삭제
    self.size -= 1          삭제했으니 사이즈 -1

 

 

 

[delete by index]

double linked list에서 index를 통한 삭제 기능 또한 삽입기능처럼, 새로운 노드를 원하는 위치까지 head 혹은 tail 통해서 접근하고, 위치index가 전체 사이즈의 반보다 앞이면 head를 통해, 뒤면 tail을 통해 접근합니다.

마찬가지로, 시간복잡도는 O(N/2)을 가집니다. (점근표기법에 따라 O(N)으로 표기)

삭제하고자하는 노드의 위치를 찾은 다음, 삭제할 노드 이전과 다음 노드를 연결해준 다음, 삭제할 노드의 연결을 끊어줍니다.

def deletebyindex(self, idx):
    prev = Node(None)
    curr = Node(None)      
    next = Node(None)
    i = 0
    if (idx < self.size/2):   #index가 헤드에서 더 가까우면
        prev = self.head
        curr = self.head.get_next()
        i += 1
        while i < idx:
            prev = prev.get_next()
            curr = curr.get_next()
        prev.set_next(curr.get_next())
        (curr.get_next()).set_prev(prev)
        curr.set_next(None)
        curr.set_prev(None)
    else:   #index가 tail에서 가까우면
        curr = self.tail.get_prev()
        next = this.tail
        while (i < (self.size-idx-1)):
            next = next.get_prev()
            curr = curr.get_prev()
        (next.get_prev()).set_prev(curr)
        (curr.get_prev()).set_next(next)
        curr.set_next(None)
        curr.set_prev(None)
    self.size -= 1

 

def deletebyindex(self, idx):
    prev = Node(None)
    curr = Node(None)       삭제하고자하는  노드
    next = Node(None)       삭제할 때는 다음 노드까지 설정
    i = 0
    if (idx < self.size/2):    index가 head에서 더 가까우면 if문 실행
        prev = self.head      삭제할 자리 찾아가기위해 head에서 부터 시작(시작이 head라서 이전 노드가 없음)
        curr = self.head.get_next()    head의 다음노드로 curr 설정
        i += 1
        while i < idx:
            prev = prev.get_next()
            curr = curr.get_next()

        prev.set_next(curr.get_next())           prev노드와 next노드 연결(next 포인터)
        (curr.get_next()).set_prev(prev)        prev노드와 next노드 연결(prev 포인터)

        curr.set_next(None)        curr(삭제하고자 했던 노드)의 next포인터 삭제
        curr.set_prev(None)        curr(삭제하고자 했던 노드)의 prev포인터 삭제
    else:    index가 tail에서 가까우면 else문 실행
        curr = self.tail.get_prev()      tail의 이전노드로 curr 설정
        next = this.tail        삭제할 자리 찾아가기위해 tail에서 부터 시작(시작이 tail라서 다음 노드가 없음)
        while (i < (self.size-idx-1)):   tail은 삭제할 수가 없으니까 -1을 해줌
            next = next.get_prev()
            curr = curr.get_prev()
        (next.get_prev()).set_prev(curr)
        (curr.get_prev()).set_next(next)
        curr.set_next(None)
        curr.set_prev(None)
    self.size -= 1     노드 삭제됐으니까 사이즈 -1

 

[전체코드]

전체코드와 다른 기능들은 깃허브를 참고하여 보실 수 있습니다.

https://github.com/sonzwon/TIL/blob/master/data_structure_List.py

GitHub - sonzwon/TIL: Today I Learned