연결 리스트 : 논리적인 순서 ≠ 물리적인 순서

단순 연결리스트 (삽입삭제방법 넣자)

원형 연결리스트

이중 연결리스트

선형 리스트의 원소의 삽입과 삭제 → 오래걸림

원소 삽입(O(n)) but 연결리스트의 경우O(1)(=연산의 크기가 상수)

원소 삭제(O(n)) but 연결리스트의 경우O(1)(=연산의 크기가 상수)

결론

선형 리스트(메모리비효율) : 데이터의 접근, 탐색이 중요할 때

연결 리스트(메모리효율) : 데이터의 추가, 삭제가 중요할 때