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

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

Section 19

단일 연결 리스트 소개

• head, tail, length 등의 특성을 가진 자료구조이다.
• 노드들로 이루어져 있으며, 각 노드는 값과 다음 노드를 가리키거나 null 값을 가진 포인터를 갖고 있다.
• 인덱스가 없어 엘리베이터가 없는 고층 건물과 같다. 원하는 값이 나올 때까지 그 앞의 모든 값을 지나쳐야 한다.
• 임의 접근이 허용되지 않고, 각 노드는 넥스트 포인터를 통해 연결되어 있다.
• 새로운 항목을 추가하거나, 기존 항목을 제거하는 데에는 인덱스가 없으므로 더 쉽게 수행할 수 있다.

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

# 연결된 노드 정의하기
first = Node('Hi')
first.next = Node('There')
first.next.next = Node('How')
first.next.next.next = Node('are')
first.next.next.next.next = Node('you')

# 연결된 노드 값 확인하기
first.val
first.next.val
first.next.next.val
first.next.next.next.val
first.next.next.next.next.val

 

push method 소개

• 주어진 값을 받아들여 새로운 노드를 만든다.
• 만약 head값이 없다면 리스트가 비어있다는 것이므로, head와 tail을 새롭게 만들어지는 노드를 가리키도록 정한다.
• 만약 리스트가 비어있지 않다면, 마지막노드의 next를 새롭게 만들어지는 노드를 가리키게 하고, tail이 새롭게 생성된 노드를 가리키도록 생성하고, 길이를 하나 늘린다.
• 그 연결 리스트를 반환한다.

pop method 소개

• 만일 리스트에 아무것도 없는 경우 undefined 를 반환한다.
• tail에 도달할 때까지 리스트에 루프를 수행한다.
• 마지막에서 두 번째 노드의 next를 null로 설정하고, tail값을 마지막에서 두 번째 노드로 설정한다.
• 리스트 길이를 하나 줄인다.
• 방금 제거한 노드를 반환한다.

shift method 소개

• 만일 리스트에 아무것도 없는 경우 undefined 를 반환한다.
• 현재 head값을 변수에 저장한다.
• head가 head의 next를 가리키도록 설정한다.
• 리스트 길이를 하나 줄인다.
• 방금 제거한 노드를 반환한다.

unshift method 소개

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

 

 

get method 소개

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

set method 소개

• 함수는 인덱스와 값을 인자로 받는다.
• 원하는 노드를 찾기 위해 get 함수를 활용한다.
  • 만약 노드를 찾을 수 없다면, False를 반환한다.
  • 만약 노드를 찾았다면, 해당 노드 값을 인자로 받아들인 값으로 정하고, True를 반환한다.

insert method 소개

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

remove method 소개

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

reverse method 소개

• head와 tail을 교환한다.
• next, prev 변수를 만들어 Null 값을 넣어둔다.`
• node변수를 만들고, head 값을 배정한다.
• 다음의 과정을 교환한 tail부터 head까지 루프를 통해 리스트 전체에 적용한다.
  • 현재 다루고 있는 값을 node 변수에 저장한다.
  • 현재 node의 .next 값을 next 변수에 저장한다.
  • 현재 node의 .next.next를 현재 node로 설정한다.
  • 현재 node 값을 prev 변수에 저장하고, node 변수에 next값을 저장하여 다루는 값을 바꾼다.

 

method 구현

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

# 단일연결리스트 class 정의
class SinglyLinkedList:
    # constructor
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

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

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

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

        self.length += 1

        return self

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

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


    # instance method
    def pop(self):
        tmp = self.head
        pre = tmp

        if tmp is None:
            return 'Undefined'

        while(tmp.next):
            pre = tmp
            tmp = tmp.next

        self.tail = pre
        self.tail.next = None

        self.length -= 1

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

        return tmp.val

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

        tmp = self.head

        self.head = tmp.next
        self.length -= 1

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

        return tmp.val

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

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

        # 리스트가 비어있지 않는 상태
        # head의 next가 현재 head를 가리키게 하고
        # head를 새로운 노드로 바꾼다
        else:
            newNode.next = self.head
            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:
            counter = 0
            tmp = self.head

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

                counter += 1

            return tmp

    # instance method
    def set(self, index, val):
        foundNode = self.get(index)
        if foundNode:
            foundNode.val = val
            return True
        return False

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

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

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

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

        newNode = Node(val)
        pre = self.get(index - 1)
        tmp = pre.next
        pre.next = newNode
        newNode.next = tmp

        self.length += 1

        return True

    # instance method
    def remove(self, index):

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

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

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

        pre = self.get(index - 1)
        tmp = pre.next
        pre.next = tmp.next

        self.length -= 1

        return tmp.val

    # instance method
    def reverse(self):

        # 현재 다룰 요소
        node = self.head
        # 다음에 다룰 요소
        next = None
        # 이전에 다룬 요소
        prev = None

        # head와 tail 교환
        self.head, self.tail = self.tail, self.head

        for i in range(self.length):
            # 다음에 다룰 요소 = 현재 노드의 .next
            next = node.next
            # 현재 노드의 .next = 이전에 다룬 요소
            node.next = prev
            # 이전에 다룬 요소 = 현재 노드
            prev = node
            # 현재노드 = 다음에 다룰 요소
            node = next

        return self
        
        
# 노드들 선언
print("---Make Node---")
L = SinglyLinkedList()
L.push('HELLO')
L.push('YOU')
L.push('GOODBYE')
L.push('!')
L.push('?')
L.push('!')

print('\n---SinglyLinkedList---')
# 노드들 출력
L.traverse()

print('\n---pop fcn---')
# pop 수행
print(L.pop())

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

print('\n---SinglyLinkedList---')
# 노드들 출력
L.traverse()

print('\n---shift fcn---')
# shift 수행
print(L.shift())

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

print('\n---SinglyLinkedList---')
# 노드들 출력
L.traverse()


print('\n---unshift fcn---')
# unshift 수행
L.unshift("Hi")

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

print('\n---SinglyLinkedList---')
# 노드들 출력
L.traverse()

print('\n---get fcn---')
# get 수행
num = 3
print('index: ', num)
print(L.get(num).val)


print('\n---set fcn---')
# set 수행
num = 3
Str = ':0'
print('index: ', num)
print('val: ', Str)
print(L.set(num, Str))

print('\n')

# set 수행
num = -1
Str = ':0'
print('index: ', num)
print('val: ', Str)
print(L.set(num, Str))

print('\n---SinglyLinkedList---')
# 노드들 출력
L.traverse()


print('\n---insert fcn---')
# insert 수행
num = 0
Str = 'WOW'
print('index: ', num)
print('val: ', Str)
print(L.insert(num, Str))

print('\n---SinglyLinkedList---')
# 노드들 출력
L.traverse()

print('\n')

# insert 수행
num = L.length
Str = 'WOW'
print('index: ', num)
print('val: ', Str)
print(L.insert(num, Str))

print('\n---SinglyLinkedList---')
# 노드들 출력
L.traverse()

print('\n')

# insert 수행
num = 3
Str = 'WOW'
print('index: ', num)
print('val: ', Str)
print(L.insert(num, Str))

print('\n---SinglyLinkedList---')
# 노드들 출력
L.traverse()

print('\n---remove fcn---')
print(L.remove(0))

print('\n---SinglyLinkedList---')
# 노드들 출력
L.traverse()

print('\n')

print(L.remove(L.length))
print(L.remove(L.length - 1))

print('\n---SinglyLinkedList---')
# 노드들 출력
L.traverse()

print('\n')

print(L.remove(3))

print('\n---SinglyLinkedList---')
# 노드들 출력
L.traverse()

print('\n---reverse fcn---')
L.reverse

print('\n---SinglyLinkedList---')
# 노드들 출력
L.traverse()

 

자료구조: 빅오 복잡도

• Insertion: O(1)
• Removal: it depends ... O(1) or O(N)
• Searching: O(N)
• Access: O(N)