연결리스트(Linked List)란?

연결리스트란 "링크를 이용해서 리스트를 만든다." 라는 뜻이다.
연결리스트는 노드로 구성되는데, 노드는 값을 담는 value와 다음 노드를 가리키는 reference로 이루어진다.

위의 사진은 노드1, 노드2, 노드3, 노드4가 순서대로 연결된 연결리스트이며, 첫 번째 노드를 head node라고 부른다.

연산별 시간복잡도

find() : O(n)
random access : 연결리스트는 random access를 지원하지 않으며, head node에서 시작해 찾으려는 노드까지 하나씩 타고 들어가야 함.
insert() : O(1)
delete() : O(1)

노드 삽입 예시

첫 번째 사진의 노드2와 노드3 사이에 노드5를 삽입하는 예시를 보자.
1) 우선 value=5를 가지는 노드5를 만든다.
2) 노드2가 노드5를 가리키도록 만든다.
3) 노드2가 가리키던 노드3을 노드5가 가리키도록 만든다.

노드 삭제 예시

첫 번째 사진의 노드3을 삭제하는 예시를 보자.
1) 노드2가 노드3이 가리키던 노드4를 가리키도록 만든다.
2) 노드3을 삭제한다.

구현

github

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

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

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

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

__init__()
연결리스트를 구성하는 노드를 초기화한다.
노드는 value, reference로 구성되며, 아직 연결된(가리키는) 노드가 없기 때문에 reference는 self.next=None이 된다.

head_node = ListNode(1)
value=1을 가지는 노드를 만들고, 순서대로 노드2, 노드3, 노드4를 만든 후 연결한다.

printNodes()
iterative 방식으로 연결 리스트를 출력한다.

printNodesRecur()
recursive 방식으로 연결 리스트를 출력한다.

참고한 강의 : 코드없는 프로그래밍