링크드 리스트(기초)

링크드 리스트는 값과 주소를 가진 노드로 이루어져있다.

탐색에 O(n) time complexity가 필요하다.

 

배열과 비교해보면 탐색에 필요한 time complexity는 같다. 그러나 random access에 필요한 값은 링크드 리스트 O(n) 배열 O(1)로 다르다.

 

insertion과 deletion에 필요한 time complexity는 O(1)이다.

 

 

 

하나의 노드가 하나의 노드에 대한 정보를 가지고 있으면 singly linked list, 두 곳의 정보를 가지고 있으면 doubly linked list라고 부른다.

 

링크드 리스트는 tree나 graph의 기본 데이터 스트럭트가 된다.

 

링크드 리스트를 python으로 구현해 본 코드

# Title : Linked List Intro

# 1. ListNode 생성
# 2. 1,2,3,4 리스트 노드 연결
# 3. Iterative Print Function
# 4. Recursive Print Function

class ListNode:
    def __init__(self, val) -> None:
        self.val = val
        self.next = None

head_node = ListNode(1)
head_node.next = ListNode(2)
head_node.next.next = ListNode(3)
head_node.next.next.next = ListNode(4)

def printNode(node: ListNode) -> None:
    crnt_node = node
    while crnt_node is not None:
        print(crnt_node.val, end=' ')
        crnt_node = crnt_node.next

printNode(head_node)

def printNodeRecur(node:ListNode) -> None:
    print(node.val, end=' ')
    if node.next is not None:
        printNodeRecur(node.next)

printNodeRecur(head_node)

 

참조 : (3) 코딩테스트, 기초, 링크드 리스트, linked list - YouTube