[251212금] 연결 리스트에 대해서 설명해주세요.

리스트 내의 요소(노드)들을 포인터로 연결하여 관리하는 선형 자료구조

각 노드는 데이터와 다음 요소에 대한 포인터를 가지고 있다.

첫 번째 노드는 HEAD, 마지맞 노드는 TAIL이라고 한다. 

메모리가 허용하는 한 계속해서 요소를 삽입할 수 있다. 

시간복잡도 : 탐색 - O(n), 삽입삭제 - O(1)

배열은 순차적인 데이터가 들어가기 때문에 메모리 영역을 연속적으로 사용하는 반면, 연결 리스트는 메모리 공간에 흩어져서 존재한다는 점에서 배열과 차이가 있다.