📖Linked List

각 노드가 데이터와 포인터를 가지고 선형으로 연결되어 있는 방식으로 데이터를 저장하는 선형 자료구조

• 데이터 : 값이 저장되는 곳
• 포인터 : 다음 노드의 주소값이 저장되는 곳
• head : Linked List의 가장 첫번째 요소
• tail : Linked List의 가장 마지막 요소

📎Single Linked List

다음 노드에 대한 참조만을 가진 가장 단순한 형태의 Linked List

📎Double Linked List

다음 노드의 참조뿐만 아니라 이전 노드의 참조도 같이 가리키는 Linked List

📎Circular Linked List

Single Linked List에서 마지막 노드가 Null 대신 처음 원소를 가리키는 Linked List

📖특징

• 데이터의 순서가 메모리에 물리적인 순서대로 저장되지는 않음
• 메모리를 미리 할당하지 않아도 되므로, 유연하게 크기 변경이 가능
• 각 데이터에 저장되어 있는 다음 데이터의 주소에 의해 연결되는 방식

📖장점

• 동적 크기
• 효율적인 메모리 사용 : 각 데이터에 저장되어 있는 다음 데이터의 주소에 의해 연결되는 방식이므로 메모리를 효율적으로 사용 가능
• 삽입/삭제의 용이 : 특정 노드의 참조만 변경하면 됨

📖단점

• 탐색의 어려움 : 순차접근만이 가능
• 메모리 오버헤드 : 각 노드는 다음 데이터의 주소를 담을 공간을 가지고 있으므로 필수적으로 추가적인 메모리를 사용
• 복잡한 구현

📖시간복잡도

연산	시간복잡도
접근	O(n)
삽입	O(1)
삭제	O(1)
탐색	O(n)

📖Array & Linked List