[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 20

* 수업은 JS 기반이지만 Python으로 구현

Section 20

이중 연결 리스트 소개

• head, tail, length 등의 특성을 가진 자료구조이다.
• 노드들로 이루어져 있으며, 각 노드는 값과 이전 노드와 다음 노드를 가리키는 포인터를 갖고 있다.
• 단일 연결 리스트보다 접근에 융통성이 있지만, 메모리를 더 많이 사용한다.

push method 소개

• 주어진 값을 받아들여 새로운 노드를 만든다.
• 만약 head 값이 비어있다면, head와 tail을 새롭게 만든 노드로 설정한다.
• 만약 리스트가 비어있지 않다면, tail의 next를 새롭게 만든 노드로 설정한다.
• 새롭게 만든 노드의 prev를 tail로 설정한다.
• tail 값을 새롭게 만든 노드로 설정한다.
• 리스트 길이를 하나 늘린다.

pop method 소개

• 만일 리스트가 비어있다면, undefined를 반환한다.
• 그렇지 않다면, 현재 tail을 반환하기 위해 변수에 저장한다.
• 만약 리스트의 길이가 1이라면, head와 tail 모두 null로 설정한다.
• tail을 prev 노드로 설정한다.
• 새로 설정된 tail의 next를 null로 설정한다.
• 원래 tail의 prev를 null로 설정하여 리스트와의 모든 연결을 해제한다.
• 리스트 길이를 하나 줄인다.
• 변수에 저장해둔 삭제한 tail을 반환한다.

shift method 소개

• 만일 리스트가 비어있다면, undefined를 반환한다.
• 그렇지 않다면, 현재 head를 반환하기 위해 변수에 저장한다.
• 만약 리스트의 길이가 1이라면, head와 tail 모두 null로 설정한다.
• head를 head의 next로 설정한다.
• head의 prev를 null로 설정한다.
• 원래 head의 next를 null로 설정하여 리스트와의 모든 연결을 해제한다.
• 리스트 길이를 하나 줄인다.
• 변수에 저장해둔 삭제한 head를 반환한다.

unshift method 소개

• 리스트 시작 위치에 추가하려는 노드를 인자로 받아들이는 함수를 정의한다.
• 만약 head값이 없다면 리스트가 비어있다는 것이므로, head와 tail을 새롭게 만들어지는 노드를 가리키도록 정한다.
• 만약 리스트가 비어있지 않다면
  • head의 prev를 새롭게 만들어지는 노드로 설정한다.
  • 새롭게 만들어진 노드의 next를 현재의 head값을 가리키게 한다.
  • head가 새롭게 생성된 노드를 가리키도록 생성하고, 길이를 하나 늘린다.
• 그 연결 리스트를 반환한다.

 

 

get method 소개

• 함수는 입력된 숫자를 인덱스 인자로 받는다.
• 인덱스 범위에 따라 다음과 같은 엣지 케이스가 있을 수 있으며, Null을 반환한다.
  • 음수
  • 리스트의 길이보다 크거나 같을 경우
• 인덱스값에 따라 head 혹은 tail을 활용한다.
  
  • 만약 인덱스가 리스트 길이의 반보다 작거나 같다면 head에서 시작해서 next를 이용한다.
  • 만약 인덱스가 리스트 길이의 반보다 크다면, tail에서 시작해서 prev를 이용한다.
• 루프를 통해 인덱스가 지정하는 위치에 이를때까지 이동한 후, 해당 인덱스 위치의 노드를 반환한다.

set method 소개

• 변수를 만들어 set 함수에 입력된 인덱스 값을 넣은 get 함수의 결과값으로 설정한다.
• get 함수가 유효한 노드값을 반환하면, 해당 노드의 값을 set 함수에 입력된 데이터 값으로 바꾼 후, True를 출력한다.

insert method 소개

• 만약 인덱스가 0보다 작거나 리스트 길이보다 크다면 False를 반환한다.
• 만약 인덱스가 리스트의 길이와 같다면, push 함수를 사용하여 리스트 마지막에 새로운 노드를 삽입한다.
• 만약 인덱스가 0이라면, unshift 함수를 활용해 리스트 맨 앞에 새로운 노드를 삽입하면 된다.
• 위의 모든 경우가 아니라면, get 함수를 활용해 인덱스 - 1 위치의 next를 생성한 새 노드로 가리키게 한다.
• 새 노드의 next를 원래 위치의 노드를, prev를 인덱스 - 1 위치를 가리키게 한다.
• 원래 위치의 노드의 prev를 새 노드를 가리키게 한다.
• 전체 길이를 1 증가시키고, True를 반환한다.

remove method 소개

• 인덱스 값이 0보다 작거나 혹은 리스트 길이보다 클 경우 Undefined를 반환한다.
• 인덱스 값이 리스트 길이 - 1과 같다면, pop 함수를 활용한다.
• 인덱스 값이 0이라면 shift 함수를 활용한다.
• 위의 모든 경우가 아니라면, get 함수를 활용해 삭제할 노드의 next와 prev를 연결한다.
• 삭제할 index 위치의 prev와 next를 Null로 설정한다.
• 리스트 길이를 1 감소하고, 제거된 노드를 반환한다.

method 구현

# 노드 정의하기
class Node:
    # constructor
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

# 이중연결리스트 class 정의
class DoublyLinkedList:
    # constructor
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    # 리스트 요소를 탐색하는 과정을 보기 위한 함수
    def traverse(self):
        tmp = self.head

        while(tmp):
            print(tmp.val)
            tmp = tmp.next


    # instance method
    def push(self, val):
        newNode = Node(val)

        # 리스트가 비어있는 상태
        if self.head is None:
            self.head = newNode
            self.tail = self.head

        # 리스트가 비어있지 않은 상태
        # 현재 tail의 next가 새로운 노드를 가리키게 하고
        # 새로운 노드의 prev가 현재 tail을 가리키게 하고
        # tail을 새로운 노드로 바꾼다
        else:
            self.tail.next = newNode
            newNode.prev = self.tail
            self.tail = newNode

        self.length += 1

        return self

    # instance method
    def pop(self):
        if self.head is None:
            return 'Undefined'

        tmp = self.tail

        if self.length == 1:
            self.head = None
            self.tail = None

        else:
            self.tail = tmp.prev
            self.tail.next = None
            # 원래 tail의 prev 값을 None으로 두어
            # 리스트와의 연결 모두를 끊어낸다.
            tmp.prev = None

        self.length -= 1

        return tmp.val

    # instance method
    def shift(self):
        if self.head is None:
            return 'Undefined'

        tmp = self.head

        if self.length == 1:
            self.head = None
            self.tail = None

        else:
            self.head = tmp.next
            self.head.prev = None
            tmp.next = None

        self.length -= 1

        return tmp.val

    # instance method
    def unshift(self, val):
        newNode = Node(val)

        if self.head is None:
            self.head = newNode
            self.tail = newNode

        else:
            tmp = self.head
            tmp.prev = newNode
            newNode.next = tmp
            self.head = newNode

        self.length += 1

        return self

    # instance method
    def get(self, index):
        self.index = index

        if (self.index < 0) or (self.length <= self.index):
            return None

        else:
            mid = int(self.length / 2)

            if self.index <= mid:
                # 확인 문구, 이후에 지우기
                # print('from head')
                counter = 0
                tmp = self.head

                while(counter != self.index):
                    tmp = tmp.next
                    counter += 1

            else:
                # 확인 문구, 이후에 지우기
                # print('from tail')
                counter = self.length - 1
                tmp = self.tail

                while(counter != self.index):
                    tmp = tmp.prev
                    counter -= 1

            return tmp

    # instance method
    def set(self, index, val):
        self.index = index

        tmp = self.get(self.index)

        if tmp is None:
            return False

        else:
            tmp.val = val
            return True

    # instance method
    def insert(self, index, val):
        self.index = index

        if (self.index < 0) or (self.length < self.index):
            return False

        elif self.index == 0:
            return not not self.unshift(val)

        elif self.index == self.length:
            return not not self.push(val)

        else:
            newNode = Node(val)
            former = self.get(self.index - 1)
            later = former.next

            former.next = newNode
            newNode.next = later
            newNode.prev = former
            later.prev = newNode

            self.length += 1
            return True

    # instance method
    def remove(self, index):
        self.index = index

        if (self.index < 0) or (self.length <= self.index):
            return 'Undefined'

        elif self.index == 0:
            return self.shift()

        elif self.index == self.length - 1:
            return self.pop()

        else:
            tmp = self.get(self.index)
            former = tmp.prev
            later = tmp.next

            former.next = later
            later.prev = former
            tmp.prev = None
            tmp.next = None

            self.length -= 1

            return tmp.val
            
            
# 노드 선언
print('---Make Node---')
DL = DoublyLinkedList()
DL.push('Hello')
DL.push('You')
DL.push('GoodBye')
DL.push('!!!')
DL.push('><')
DL.push('><')

print('\n---Double Linked List---')
DL.traverse()

print('\n---pop fcn---')
print(DL.pop())

# 리스트 tail, 리스트 길이 출력
print('tail: ', DL.tail.val)
print('length: ', DL.length)

print('\n---Double Linked List---')
DL.traverse()

print('\n---shift fcn---')
print(DL.shift())

# 리스트 head, 리스트 길이 출력
print('head: ', DL.head.val)
print('length: ', DL.length)

print('\n---Double Linked List---')
DL.traverse()

print('\n---unshift fcn---')
DL.unshift(':)')

# 리스트 head, 리스트 길이 출력
print('head: ', DL.head.val)
print('length: ', DL.length)

print('\n---Double Linked List---')
DL.traverse()

print('\n---get fcn---')
num = DL.length
print('num: ', num)
print(DL.get(num))

print('\n')

num = -3
print('num: ', num)
print(DL.get(num))

print('\n')

num = 1
print('num: ', num)
print(DL.get(num).val)

# get 함수에서 주석을 해제하면, head에서 시작한지 tail에서 시작했는지 확인할 수 있음
print('\n---get fcn check---')
for i in range(DL.length):
    DL.get(i).val

print('\n---set fcn---')
print(DL.set(5, ';/'))
DL.traverse()

print('\n')

print(DL.set(4, ';/'))
DL.traverse()

print('\n---insert fcn---')
num = 8
print('num: ', num)
print(DL.insert(num, '=t='))
print('length: ', DL.length)
DL.traverse()

print('\n')
num = 0
print('num: ', num)
print(DL.insert(0, '=t='))
print('length: ', DL.length)
DL.traverse()

print('\n')
num = DL.length
print('num: ', num)
print(DL.insert(num, '=t='))
print('length: ', DL.length)
DL.traverse()

print('\n')
num = 5
print('num: ', num)
print(DL.insert(num, '=t='))
print('length: ', DL.length)
DL.traverse()

print('\n---remove fcn---')
num = -10
print('num: ', num)
print(DL.remove(num))
DL.traverse()

print('\n')
num = 10
print('num: ', num)
print(DL.remove(num))
DL.traverse()

print('\n')
num = 0
print('num: ', num)
print(DL.remove(num))
DL.traverse()

print('\n')
num = DL.length - 1
print('num: ', num)
print(DL.remove(num))
DL.traverse()

print('\n')
num = 3
print('num: ', num)
print(DL.remove(num))
DL.traverse()

자료구조: 빅오 복잡도

• Insertion: O(1)
• Removal: it depends ... O(1)
• Searching: O(N) technically, O(N/2)
• Access: O(N)