linked-list

Linked List란 무엇인가?

연결 리스트는 각 데이터(노드)가 다음 데이터의 위치를 가리키는 포인터로 이어진 자료구조다. 배열과 달리 메모리 상에 흩어져 있으며, 맨 앞부터 순서대로만 접근할 수 있다. 보물찾기 단서처럼 하나를 찾으면 다음 위치를 알려주는 구조다.

Linked list is a linear data structure that stores data in nodes, which are connected by pointers. Unlike arrays, nodes of linked lists are not stored in contiguous memory locations and can only be accessed sequentially, starting from the head of list.

Linked List와 Array의 차이는?

배열은 데이터가 메모리에 나란히 저장되어 원하는 위치에 바로 접근할 수 있지만, 중간에 끼워넣거나 빼기가 어렵다. 연결 리스트는 반대로, 순서대로만 접근 가능하지만 중간 삽입/삭제가 빠르다.

Feature Linked List Array
Data Structure Non-contiguous Contiguous
Memory Allocation Typically allocated one by one to individual elements Typically allocated to the whole array
Insertion/Deletion Efficient Inefficient
Access Sequential Random

Feature	Linked List	Array
Data Structure	Non-contiguous	Contiguous
Memory Allocation	Typically allocated one by one to individual elements	Typically allocated to the whole array
Insertion/Deletion	Efficient	Inefficient
Access	Sequential	Random

Linked List의 종류는?

이중 연결 리스트(DLL)는 앞뒤 양방향으로 이동할 수 있어 삽입/삭제가 편리하다. 원형 연결 리스트(CLL)는 마지막 노드가 다시 처음으로 연결되어 순환 구조를 이루며, 끝없이 반복 순회해야 하는 경우에 유용하다.

Doubly Linked List (DLL): Doubly linked lists allow for efficient traversal of the list in both directions, making it suitable for applications where frequent insertions and deletions are required.

Circular Linked List (CLL): We can traverse the list from any node and return to it without needing to restart from the head, which is useful in applications requiring a circular iteration. In a circular linked list, each node has a reference to the next node in the sequence. Although it doesn't have a direct reference to the previous node like a doubly linked list, we can still find the previous node by traversing the list.

Doubly Linked List가 Singly Linked List 대비 삽입/삭제에서 유리한 점은?

이중 연결 리스트는 각 노드가 앞 노드와 뒷 노드 모두를 알고 있어, 삽입이나 삭제 시 리스트 전체를 처음부터 탐색할 필요가 없다. 단방향 리스트에서는 이전 노드를 찾으려면 처음부터 다시 따라가야 한다.

Easy insertion and deletion of nodes: The presence of pointers to both the previous and next nodes makes it easy to insert or delete nodes from the list, without having to traverse the entire list.