➡️ Linked List

intro

➡️ Linked List(연결 리스트)는 배열이라는 자료구조와 비교하며 이해하면 쉽다. 연결 리스트는 배열과 달리 연속된 메모리 공간에 데이터를 저장하지 않고, 각 데이터가 다음 데이터의 위치를 가리키는 방식으로 저장한다. (선형 자료 구조). 이 때의 각 데이터 단위를 node라고 하고, node는 데이터를 저장하고, 다음 노드를 가리키는 참조(주소)를 포함한다.

 

➡️ 연결 리스트는 아래와 같은 3가지 특징이 존재한다.

① 동적 크기: 배열과 달리 연결 리스트는 크기가 고정 x. 따라서 노드를 언제나 추가 / 삭제를 쉽게 할 수 있어 크기가 가변적.

② 삽입 / 삭제 쉬움: 배열의 경우 삽입 / 삭제 연산을 진행할 때 해당 위치 이후의 모든 요소를 이동시켜야 하는 번거로움이 있으나, 연결 리스트는 연결된 링크만 변경하면 되므로 매우 효율적

③ 메모리 효율성: 배열은 저장하기 위한 메모리 공간을 미리 할당. 하지만 연결 리스트는 그 때에 따라 필요한 만큼만 메모리를 할당하므로 메모리 낭비 줄일 수 있음

 

➡️ 아래 그림 참조

: Node class에 값을 저장하는 data와 그 다음 Node를 가리키는 next가 존재. next는 None으로 설정. Node __init__의 입력으로는 data 1개만 존재. head.next ~ / head.next.next ~ 이렇게 next를 붙이면서 연결 리스트로 node와 node 사이 연결

 

➡️ linked list 값 출력(while node로 돌리면 된다)

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

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

node = head
while node:
    print(node.data, end=' ') #1 2 3
    node = node.next

 

➡️ linked list의 끝에 새 노드를 추가하기(while문으로 쭉 돌리며 node.next 최종적으로 가리키는 곳을 node로 설정. 이후 node가 마지막 node를 가리키는 객체가 되면, node.next에 Node(4)로 추가)

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

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

node = head
while node:
    node = node.next
node.next = Node(4)

 

➡️ linked list 처음에 새 노드를 추가하기(Node(0)으로 만든 객체가 head를 가리키게 하기 위해 node.next = head 설정. head를 새롭게 만든 node로 update)

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

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

node = Node(0)
node.next = head
head = node

node = head
while node:
    print(node.data, end=' ')
    node = node.next

Linked List Class

① Linked List Class 준비

: 앞서 만든 Node class 활용 / __init__()에는 연결 리스트에 접근하기 위해 필요한 head, 그리고 연결 리스트의 길이 length 속성 각각 None과 0 설정 / 특수 메서드 __len__()에는 길이를 반환하는 length 출력

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

class LinkedList:
    def __init__(self):
        self.head = None
        self.length = 0
    
    def __len__(self):
        return self.length

② appendleft()

: linked list 맨 앞에 node 추가하는 함수. 즉, head가 None이라면 생성 노드를 바로 head에 할당. head가 None이 아니라면 노드 생성 후 생성한 node의 next에 head 할당. 그 다음 head를 새로 만든 노드로 옮긴다. / linked list 길이 1 증가

def appendleft(self, data):
    if self.head is None:
        self.head = Node(data)
    else:
        node = Node(data)
        node.next = self.head
        self.head = node
    self.length += 1

if __name__ == "__main__":
    l = LinkedList()
    print(f'Linked List Created. Length of a linked list = {len(l)}')
    for i in range(4):
        l.appendleft(1)
        print(f'{i} added. Length of a linked list = {len(l)}')

'''
Linked List Created. Length of a linked list = 0
0 added. Length of a linked list = 1
1 added. Length of a linked list = 2
2 added. Length of a linked list = 3
3 added. Length of a linked list = 4
'''

③ append()

: linked list 맨 오른쪽에 node 추가하는 함수. 즉, head가 None이며 생성한 노드를 head에 할당. head가 None이 아니면 임시 노드를 만들어 마지막 노드까지 이동. 그 다음 새 노드를 만든 뒤, 임시 노드의 next에 새 노드 할당.

def append(self, data):
    if self.head is None:
        self.head = Node(data)
    else:
        node = self.head
        while node.next is not None:
            node = node.next
        node.next = Node(data)
    self.length += 1

④ print status

: 특수 메서드인 __str__을 구현하여 print() 함수로 연결 리스트의 상태 출력

def __str__(self):
    if self.head is None:
        return 'Linked list is empty!'
    res = "Head"
    node = self.head
    while node is not None:
        res += ' -> ' + str(node.data)
        node = node.next
    return res
    
if __name__ == "__main__":
    l = LinkedList()
    print(f'Linked List Created. Length of a linked list = {len(l)}')
    print(l)
    for i in range(4):
        l.appendleft(i)
        print(f'{i} added. Length of a linked list = {len(l)}')
        print(l)

'''
Linked List Created. Length of a linked list = 0
Linked list is empty!
0 added. Length of a linked list = 1
Head -> 0
1 added. Length of a linked list = 2
Head -> 1 -> 0
2 added. Length of a linked list = 3
Head -> 2 -> 1 -> 0
3 added. Length of a linked list = 4
Head -> 3 -> 2 -> 1 -> 0
'''

⑤ searching a value

: 특수 메서드 __str__()을 활용하여(in 연산자) head부터 끝까지 돌면서 원하는 값이 있는 지 확인

def __contains__(self, target):
    if self.head is None:
        return False
    node = self.head
    while node is not None:
        if node.data == target:
            return True
        node = node.next
    return False
    
 if __name__ == "__main__":
    import random
    data = list(range(10,20))
    random.shuffle(data)
    l = LinkedList()
    for i in data:
        l.append(i)
    print(f'Linked List Status:\n{l}')
    for _ in range(4):
        i = random.randint(5, 25)
        if i in l:
            print(f'{i} is in the Linked List')
        else:
            print(f'{i} is not in the Linked List')

'''
Linked List Status:
Head -> 13 -> 17 -> 11 -> 18 -> 14 -> 16 -> 12 -> 19 -> 10 -> 15
17 is in the Linked List
20 is not in the Linked List
24 is not in the Linked List
21 is not in the Linked List
'''

⑥ popleft()

: head가 None이면 None 반환. None이 아니라면 임시 노드를 만들고(node = self.head) 임시 노드에 head 할당. head를 head의 다음 노드로 이동(self.head = self.head.next). (임시노드에 원래의 head를 할당하면, 임시 노드로 첫 할당된 노드는 프로그램에서 더이상 사용 x, garbage collection에 의해 자동으로 메모리에서 해제된다)

def popleft(self):
    if self.head is None:
        return None
    node = self.head
    self.head = self.head.next
    self.length -= 1
    return node.data
    
if __name__ == "__main__":
    import random
    data = list(range(10,15))
    random.shuffle(data)
    l = LinkedList()
    for i in data:
        l.append(i)
    print(f'Linked List Status:\n{l}')
    print()
    for _ in range(len(l)):
        print(f'after {l.popleft()} .. length = {len(l)}, {l}')
    print(f'when the linked list became empty, the emptied values is {l.popleft()}')

'''
Linked List Status:
Head -> 13 -> 17 -> 11 -> 18 -> 14 -> 16 -> 12 -> 19 -> 10 -> 15
17 is in the Linked List
20 is not in the Linked List
24 is not in the Linked List
21 is not in the Linked List
'''

⑦ pop()

: linked list의 맨 오른쪽을 빼는 연산은, (1) 아예 node가 한 개도 존재하지 않는 경우, (2) node가 단 1개만 존재하는 경우, 그리고 (3) node가 2개 이상 존재하는 경우로 나눌 수 있다.

: (2)의 경우 head 자체를 None으로 가리켜 pop 연산 진행 / (3)의 경우 prev를 None으로 가리켜 pop 연산 진행

def pop(self):
    if self.head is None:
        return None
    node = self.head
    while node.next is not None:
        prev = node
        node = node.next
    if node == self.head:
        self.head = None #pop
    else:
        prev.next = None #pop
    self.length -= 1
    return node.data
    
if __name__ == "__main__":
    import random
    data = list(range(10,15))
    random.shuffle(data)
    l = LinkedList()
    for i in data:
        l.append(i)
    print(f'Linked List Status:\n{l}')
    for _ in range(len(l)):
        print(f'after popping {l.pop()} .. length = {len(l)}, {l}')
    print(f'when the linked list became empty, the popped value is {l.pop()}')

'''
Linked List Status:
Head -> 12 -> 11 -> 13 -> 14 -> 10
after popping 10 .. length = 4, Head -> 12 -> 11 -> 13 -> 14
after popping 14 .. length = 3, Head -> 12 -> 11 -> 13
after popping 13 .. length = 2, Head -> 12 -> 11
after popping 11 .. length = 1, Head -> 12
after popping 12 .. length = 0, Linked list is empty!
when the linked list became empty, the popped value is None
'''

⑧ remove()

: 원하는 값을 삭제하는 연산이다. 현재 노드 node와 그 전의 노드 prev 이렇게 2개의 노드가 주어진 상태에서, 삭제하고자 하는 값이 존재한다면, 그 전의 노드 prev와 그 다음 노드를 연결하고 True 리턴. 삭제하고자 하는 값이 존재하지 않는다면 False 리턴

: while문의 조건으로 node is not None이고 node.data != target인 동안 돌려 삭제하고자 하는 node와 그 이전 node를 prev로 설정. linked list에 원래 node가 없거나 삭제하고자 하는 node가 없다면 node는 None / 그렇지 않다면 삭제하고자 하는 node가 있음. 이 때 node 개수가 1개라면 self.head를 None으로 설정 / 개수가 2개 이상이라면 prev.next = node.next로 설정

def remove(self, target):
    node = self.head
    while node is not None and node.data != target:
        prev = node
        node = node.next

    if node is None: #no target exists
        return False

    if node == self.head: #target exists but only 1 node
        self.head = self.head.next
    else: #target exists but more than 1 node
        prev.next = node.next

    self.length -= 1
    return True

⑨ insert()

: 삽입하고자 하는 곳이 맨 처음과 맨 끝이면 앞에서 만든 append()와 appendleft() 사용. 맨 처음과 맨 끝이 아니면 아래 그림과 같이 삽입하고 자 하는 위치까지 node 이동 후, node의 next로 가리키는 화살표를 끊고 node.next를 new_node.next로 바꾼다 / 그리고 기존 node의 next가 가리키는 부분을 새 노드 new_node로 가리키게 한다. (new_node.next = node.next / node.next = new_node)

def insert(self, i, data):
    if i<=0:
        self.appendleft(data)
    elif i>=self.length:
        self.append(data)
    else:
        node = self.head
        for _ in range(i-1):
            node = node.next
        new_node = Node(data)
        new_node.next = node.next
        node.next = new_node
        self.length += 1

⑩ reverse()

: in-place reversal로 새로운 메모리를 위한 리스트를 생성해서 기존 리스트의 노드 연결만 변경하는 방식으로 reverse() 구현.

현재 node를 가리키는 head 바로 앞을 prev, 바로 뒤를 ahead라고 했을 때, head가 가리키는 뒤는 ahead이지만, 이를 바꾸어 head가 가리키는 곳을 prev로 바꾼다. 이를 ahead가 None을 가리킬 때까지 계속 진행. 이후 다 진행하고 난 뒤, 맨 마지막 노드의 head가 바로 앞의 node를 가리키게끔 한 번 더 업데이트 해주어야 head 시작점에 맞게 최종 linked list 완성!(마지막에 한 번 더 업데이트 하는 이유는 아래 그림 참조)

def reverse(self):
    if self.length < 2:
        return
    prev, ahead = None, self.head.next
    while ahead:
        self.head.next = prev #reverse!
        prev = self.head #prev update
        self.head = ahead #head update
        ahead = ahead.next #ahead update
        print(self)
    self.head.next = prev #last node: make sure head positioned properly

Exercises

TBD