SSL - Singly Linked List

[탄생 배경]

배열은 유연하게 크기를 변경하기 어려운 자료구조로 크기를 유연하게 바꿀 수 있는 데이터를 보관하는 자료구조를 필요로 하게 됨.

[구성 요소]

Node: List내의 각 요소 / data와 다음 노드에 대한 pointer 정보를 포함
Head: List의 첫번째 node
Tail: List의 마지막 node

[주요 연산]

• node 생성/소멸
• node 추가
• node 탐색
• node 삭제
• node 삽입

시간 복잡도

주요 연산	Time Complexity
생성/소멸	O(1)
추가	O(1) (tail을 알고 있는 경우) / O(N) (tail을 모르고 있는 경우)
탐색	O(N)
삭제	O(1) (해당 node를 알고 있는 경우)
삽입	O(1) (알고 있는 node의 뒤에 삽입하는 경우) / O(N) (특정 위치 혹은 node의 뒤에 삽입하는 경우)

[장점]

• node의 추가/삽입/삭제가 빠름

[단점]

• 다음 node를 가리키는 pointer 저장을 위한 메모리
• 탐색의 경우 O(N)으로 느린 편

[주의]

정적 메모리 (static memory)
자동 메모리 (automatic memory)
자유 저장소 (free store)
중 자유 저장소 즉 heap영역에 node를 생성해야 한다.
그렇지 않으면 메모리가 해제되어 버리는 문제가 발생한다.

[Code Implementation]

https://github.com/han811/taehan/tree/main/algo/ch1_list/1_1_SSL