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