TIL_34 : 더블리 링크드 리스트

🙄 더블리 링크드 리스트

---

➡ 더블리 링크드 리스트란?

• 각 노드가 다음 노드의 레퍼런스, 전 노드의 레퍼런스 모두 저장하고 있는 링크드 리스트

class Node:
    """링크드 리스트 노드"""
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None


class LinkedList:
    """링크드 리스트"""
    def __init__(self):
        self.head = None
        self.tail = None

🙄 더블리 링크드 리스트 연산

---

➡ 싱글리 링크드 리스트와의 공통 연산

• 접근/탐색 연산, __str__ 메소드는 싱글리 링크드 리스트랑 동일

➡ 더블리 링크드 리스트 추가 연산 : append

class Node:
    """링크드 리스트 노드"""
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None


class LinkedList:
    """링크드 리스트"""
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        """링크드 리스트 추가 연산 메소드"""
        new_node = Node(data) 		# 새로운 데이터를 저장하는 노드
        				
        if self.head is None:		# 링크드 리스트가 비어 있는 경우
            self.head = new_node
            self.tail = new_node
        else:   			# 데이터가 이미 있는 경우
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
  

# 빈 링크드 리스트 정의
my_list = LinkedList()

# 링크드 리스트에 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)

print(my_list)

# | 2 | 3 | 5 | 7 |

👉 리스트 가장 앞에는 삽입할 수 없다는 단점
👉 이를 보완하는 prepend 메소드를 작성해보자

➡ 더블리 링크드 리스트 추가 연산 : prepend

class LinkedList:
    """링크드 리스트"""
    def __init__(self):
        self.head = None
        self.tail = None

    def prepend(self, data):
        """링크드 리스트 가장 앞에 데이터를 추가시켜주는 메소드"""
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.head.prev = new_node
            new_node.next = self.head
            self.head = new_node


# 새로운 링크드 리스트 생성
my_list = LinkedList()

# 여러 데이터를 링크드 리스트 앞에 추가
my_list.prepend(11)
my_list.prepend(7)
my_list.prepend(5)
my_list.prepend(3)
my_list.prepend(2)

print(my_list) 	# 링크드 리스트 출력

# head, tail 노드가 제대로 설정됐는지 확인
print(my_list.head.data)
print(my_list.tail.data)

# | 2 | 3 | 5 | 7 | 11 |
# 2
# 11

➡ 더블리 링크드 리스트 삭제 연산

• 4가지 경우 고려
  1. 리스트 길이가 1일 때
  2. head 노드를 지울 때
  3. tail 노드를 지울 때
  4. 두 노드 사이 노드를 지울 때

class LinkedList:
    """링크드 리스트"""
    def __init__(self):
        self.head = None
        self.tail = None

    def delete(self, node_to_delete):
        """더블리 링크드 리스트 삭제 연산 메소드"""
        data = node_to_delete.data

        if self.head is self.tail:
            self.head = None
            self.tail = None
        elif self.head is node_to_delete:
            self.head = self.head.next
            self.head.prev = None
        elif self.tail is node_to_delete:
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            node_to_delete.next.prev = node_to_delete.prev
            node_to_delete.prev.next = node_to_delete.next
        return data

    def find_node_at(self, index):
        """링크드 리스트 접근 연산 메소드. 파라미터 인덱스는 항상 있다고 가정"""

        iterator = self.head

        for _ in range(index):
            iterator = iterator.next

        return iterator

 

# 새로운 링크드 리스트 생성
my_list = LinkedList()

# 새로운 노드 4개 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)

print(my_list)

# 두 노드 사이에 있는 노드 삭제
node_at_index_2 = my_list.find_node_at(2)
my_list.delete(node_at_index_2)
print(my_list)

# 가장 앞 노드 삭제
head_node = my_list.head
print(my_list.delete(head_node))
print(my_list)

# 가장 뒤 노드 삭제
tail_node = my_list.tail
my_list.delete(tail_node)
print(my_list)

# 마지막 노드 삭제
last_node  = my_list.head
my_list.delete(last_node)
print(my_list)

# | 2 | 3 | 5 | 7 |
# | 2 | 3 | 7 |
# 2
# | 3 | 7 |
# | 3 |
# |

🙄 더블리 링크드 리스트 시간 복잡도

---

더블리 링크드 리스트 시간 복잡도

연산	링크드 리스트
접근	$O(n)$
탐색	$O(n)$
삽입	$O(1)$
삭제	$O(1)$

현실적인 시간 복잡도

연산	링크드 리스트
접근	$O(n)$
탐색	$O(n)$
원하는 노드에 접근 또는 탐색 + 삽입	$O(n+1)$
원하는 노드에 접근 또는 탐색 + 삭제	$O(n+1)$

삽입 & 삭제 연산 특수 경우

연산	더블리 링크드 리스트
가장 앞에 접근 + 삽입	$O(1+1)$
가장 앞에 접근 + 삭제	$O(1+1)$
가장 뒤에 접근 + 삽입	$O(1+1)$
가장 뒤에 접근 + 삭제	$O(1+1)$

싱글리 vs 더블리 링크드 리스트 tail 노드 삭제

연산	싱글리 링크드 리스트	더블리 링크드 리스트
가장 앞에 접근 + 삽입	$O(1+1)$	$O(1+1)$
가장 앞에 접근 + 삭제	$O(1+1)$	$O(1+1)$
가장 뒤에 접근 + 삽입	$O(1+1)$	$O(1+1)$
가장 뒤에 접근 + 삭제	$O(n+1)$	$O(1+1)$

👉 tail 노드를 지우기 위해 이전 노드에 접근해야 하는 싱글리
👉 속성으로 저장된 tail 노드를 파라미터로 받는 더블리

• 링크드 리스트를 사용해야 되는 상황에서 tail 노드를 많이 삭제해야 된다면 ❓
  ➡ 싱글리 리스트보다 더블리 링크드 리스트가 효율적

🙄 싱글리 vs 더블리 링크드 리스트

---

• 싱글리 : 특정 노드에서 앞에 있는 노드들에 접근할 수 없다
• 더블리 : 어떤 노드든지 링크드 리스트 안 모든 노드에 접근할 수 있다

추가적 공간

• 자료 구조가 사용하는 공간 중 실제 저장하려는 데이터를 제외한 다른 정보가 저장된 공간
  ex) 레퍼런스 저장 공간
• 싱글리 : 노드가 n개일 때 n-1개의 레퍼런스 저장, $O(n)$의 추가적 공간 복잡도
• 더블리 : 노드가 n개일 때 2n-2개의 레퍼런스 저장, $O(n)$의 추가적 공간 복잡도

👉 같은 공간 복잡도 : $O(n)$ 를 갖지만 실제로는 2배 차이
👉 평소에는 큰 차이 없지만 진짜 공간을 효율적이게 사용하고 싶다면 싱글리가 효율적