노드를 주소로 연결한 자료구조
node: 데이터의 단위로, 값과 포인터(다음 노드나 이전 노드의 연결 정보)로 구성되어 있다 (노드의 값 여러개/형태 가능,링크 여러개 가능 -> 하지만 그렇다면 더이상 링크드리스트는 아니다. )
head: 첫 노드
tail: 마지막 노드
배열의 메모리 사용과 수정 어렵다는 단점을 해결하기 위해 나온 자료구조로, 배열과 다르게 추가/삭제가 더 용이하다. (이때, 구현이 쉽다는 것이 아니라 메모리 관리가 용이한 것이다.)
주의점: 링크 정보 유실되지 않게 조심해야 한다. (지우기 전 연결해놓자!)
데이터 추가: 추가할 노드 생성 → 첫 노드부터 순차적으로 위치 찾고 연결 작업→ 필요 시, head/tail 이전
데이터 삭제: 첫 노드부터 순차적으로 순회해 지울 노드 지정 (delete_node) → (필요시 head/tail 이전) → 삭제 노드 전/후의 노드의 연결 작업→ delete_node 삭제
링크드리스트는 연속공간에 저장하는 대신, 키로 주소를 찾아가는 형태라, 배열보다는 접근 속도가 느리다. 이유는, 주소를 처음부터 차근차근 추적해 찾으니까, 데이터가 인접해있지 않은 경우 찾는 시간이 필요하기 때문이다.