Data structures (with python) - 4. Linked List

Data structures (with python) - 4. Linked List

 

💡 Arrays store elements in contiguous memory locations, resulting in easily calculable addresses for the elements stored and this allows faster access to an element at a specific index. Linked lists are less rigid in their storage structure and elements are usually not stored in contiguous locations, hence they need to be stored with additional tags giving a reference to the next element. This difference in the data storage scheme decides which data structure would be more suitable for a given situation.

배열은 요소를 인접한 메모리 위치에 저장하므로 저장된 요소의 주소를 쉽게 계산할 수 있어 특정 인덱스의 요소에 더 빠르게 액세스할 수 있습니다. 링크된 목록은 저장 구조가 덜 엄격하고 일반적으로 요소가 인접한 위치에 저장되지 않으므로 다음 요소를 참조할 수 있는 추가 태그와 함께 저장해야 합니다. 이러한 데이터 저장 체계의 차이에 따라 주어진 상황에 더 적합한 데이터 구조가 결정됩니다.

 

연결 리스트(Linked List)는 데이터 요소들이 메모리의 연속적인 위치에 저장되지 않고, 

각 요소(node)가 다음 요소를 가리키는 방식으로 구성된 자료구조 입니다.

Linked list의 각 노드는 두 부분으로 구성되어 있습니다. 

1. 데이터를 저장하는 부분

2. 다음 노드를 가리키는 부분(링크 또는 포인터) 입니다.

 

Linked list 의 특징

- 노드는 메모리의 어느 곳이든 배치될 수 있다.

이는 array 와 대조적인 특징으로, array의 요소들은 연속적인 메모리 위치에 배열된다.

 

- 코드의 삽입과 삭제가 상대적으로 간단합니다.

이는 삽입 또는 삭제할 노드의 링크만 변경하면 되기 떄문이다.

하지만 이를 위해서는 삽입 또는 삭제할 노드의 이전 노드를 알아야 합니다.

 

- 배열과는 달리 linked list의 크기는 동적으로 변할 수 있다.

 

 

In Pyhton

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

노드를 표현하는 클래스를 생성합니다.

 

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = Node(data)

    def display(self):
        elements = []
        current_node = self.head
        while current_node:
            elements.append(current_node.data)
            current_node = current_node.next
        print(elements)

그 후, Linked list를 표현하는 클래스를 생성한다.

 

linked_list = LinkedList()
linked_list.append('A')
linked_list.append('B')
linked_list.append('C')
linked_list.display()  # 출력: ['A', 'B', 'C']

이와 같이 파이썬에서 Linked list를 구현할 수 있다.

 

 

알고리즘 활용

주로 '병합 정렬(merge sort)' 에 사용된다.

병합 정렬은 분할정복(Divide and Conquer) 전략을 이용한 알고리즘으로,

원소들을 가장 작은 단위로 분할한 후 병합하면서 정렬하는 방식이다.

이 떄, Linked list는 분할과 병합 과정에서 요소의 삽입과 삭제가 효율적이라는 이점을 살려 이 과정을 빠르게 처리한다.

 

1. 분할 단계에서는 Linked list를 반으로 나누는 작업이 이루어진다.

이 작업은 

빠른 포인터( 한 번에 두칸 씩 이동) a.k.a 토끼

느린 포인터( 한번에 한 칸씩 이동) a.k.a 거북이

을 사용해서 리스트의 중간을 찾고, 리스트의 두 부분으로 분할합니다

 

2. 병합 단계에서 두 개의 정렬된 리스트를 하나의 정렬된 리스트로 병합한다.

이 과정에서 두 리스트의 머리부터 비교하면서 작은 값을 선택해, 새로운 리스트에 추가하고,

선택된 노드를 다음 노드로 이동시킨다.

 

이 외에는

체이닝 (해시 테이블의 충돌처리 방법중 하나),

LRU(Least Recnetly Used) 캐시 등 에 활용된다.

 

코테 공략

 

1. 두 수의 덧셈

두 개의 Linked list 가 주어지며,

각 list의 노드는 숫자의 각 자릿수를 표현한다. 두 linked list를 더하여 새로운 Linked list를 생성하는 문제입니다.

각 자리수의 연산과 올림을 처리해야 하므로 linked list의 순회 및 노드 관리 능력을 테스트.

 

2. 순환 Linked list 판별

주어진 Linked list가 순환하는지 ( = 노드가 자기 자신을 다시 가리키는지) 판별하는 문제

순환을 판별하기위해 Floyd's cycle detection algorithm을 사용한다.

참고 : https://snutiise.github.io/Floyd's-Cycle-Detection-Algorithm/

플로이드 순환 찾기 알고리즘 Floyd's Cycle Detection Algorithm

 

"토끼와 거북이" 알고리즘을 이용해 순환 연결리스트를 판별을 파이썬에서 해보자.

 

# linked list 구현
class Node:
    def __init__(self, x):
        self.val = x
        self.next = None

 

def has_cycle(head):
    if head is None:
        return False

    slow = head  # 거북이
    fast = head  # 토끼

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:  # 거북이와 토끼가 만나면 순환 있다고 판단
            return True

    return False

위 함수는 토끼와 거북이가 같은 노드를 가리킬 때 순환을 감지한다.

토끼는 두칸씩, 거북이는 한 칸 씩 이동합니다.

만약 순환이 존재한다면 토끼는 결국 거북이를 따라 잡는다. 는 가정을 본다.

 

# Linked list 생성
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = head.next  # 순환 생성

# 순환 여부 테스트
print(has_cycle(head))  # True가 출력되어야 함

위 코드에서는 순환 연결 리스트를 생성하고, 순환 여부 테스트한다.

마지막 노드가 2번쨰 노드를 가리키도록 설정해 순환을 만들었습니다.

 

따라서 has_cycle은 True가 나온다.