[알고리즘] 패스트캠퍼스 알고리즘 학습 정리 - 더블 링크드 리스트(Double Linked List)

목차

다양한 링크드 리스트 구조

1. 더블 링크드 리스트 (Doubly linked list)

• 더블 링크드 리스트 기본 구조

  • 이중 연결 리스트라고도 함
  • 단방향 링크드리스트인 경우 가장 끝 노드를 찾기 위해서는 처음부터 끝까지 모든 노드를 지나서 검색해야하는 한계가 있다.
  • 데이터가 뒷쪽에 더 가깝다는 것을 안다면 뒤에서부터 검색하면 더 빠르게 접근할 수 있다.
  • 장점 : 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
  • 단점 : 앞쪽 주소와 뒷쪽 주소를 모두 저장해야함. 저장 효율이 낮아진다.

![](https://www.fun-coding.org/00_Images/doublelinkedlist.png) (출처: wikipedia, https://en.wikipedia.org/wiki/Linked\_list)

---

2. 더블 링크드 리스트 Search

기존 소스코드

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

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head

    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            new.prev = node
            node.next = new
            self.tail = new

    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next

Search From Head & Search From Tail

# Head와 Tail 부분에서 부터 찾기 시작하는 함수
def search_from_head(self, data):
    node = self.head

    while node:
        if node.data == data:
            return node
        else:
            node = node.next
    return False

def search_from_tail(self, data):
    node = self.tail

    while node:
        if node.data == data:
            return node
        else:
            node = node.prev
    return False

# 확인하기
double_linked_list = NodeMgmt(0)

for data in range(1,10):
    double_linked_list.insert(data)
double_linked_list.desc()

print("----------------")

print(double_linked_list.search_from_head(3).data)
print(double_linked_list.search_from_head(7).data)

>>>
0
1
2
3
4
5
6
7
8
9
----------------
3
7

Insert_before, 노드 앞쪽에 데이터 추가하기

def insert_before(self, data, before_data):
    if self.head==None:
        self.head = Node(data)
        return True
    else:
        node = self.tail
        new_node = Node(data)
        while node.data != before_data:
            node = node.prev
            if node == None:
                return False

        node.prev.next = new_node
        new_node.prev = node.prev
        new_node.next = node
        node.prev = new_node
        return True

# 확인하기
double_linked_list.insert_before(999, 7) # 7 이전에 999값 넣기
double_linked_list.desc()

>>>
0
1
2
3
4
5
6
999
7
8
9

---

3. 링크드 리스트 : 전체 소스 코드

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

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head

    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            new.prev = node
            node.next = new
            self.tail = new

    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next

    def search_from_head(self, data):
        node = self.head

        while node:
            if node.data == data:
                return node
            else:
                node = node.next
        return False

    def search_from_tail(self, data):
        node = self.tail

        while node:
            if node.data == data:
                return node
            else:
                node = node.prev
        return False

    def insert_before(self, data, before_data):
        if self.head==None:
            self.head = Node(data)
            return True
        else:
            node = self.tail
            new_node = Node(data)
            while node.data != before_data:
                node = node.prev
                if node == None:
                    return False

            node.prev.next = new_node
            new_node.prev = node.prev
            new_node.next = node
            node.prev = new_node
            return True

[알고리즘] 패스트캠퍼스 알고리즘 학습 정리 - 자료구조란?

[알고리즘] 패스트캠퍼스 알고리즘 학습 정리 - 스택이란?

[알고리즘] 패스트캠퍼스 알고리즘 학습 정리 - 링크드 리스트(Linked List)