단일 연결 리스트
각 노드가 다음 노드만 안다. 구조는 가볍지만 삭제할 때 이전 노드를 찾아야 한다.
장점링크가 하나라 단순
비용이전 노드 탐색 O(N)
LINKED LIST
연결 리스트는 값 이동 대신 링크를 바꿔 중간 수정 비용을 줄인다
선택 기준은 단순하다. 임의 접근이 많으면 배열, 중간 삽입/삭제가 많으면 연결 리스트를 검토한다.
이중 연결 리스트
앞뒤 링크를 모두 유지한다. 대상 노드를 알고 있으면 양쪽 링크만 바꿔 제거한다.
장점양방향 이동 가능
비용prev 관리 오버헤드
삽입/삭제 많음노드 위치를 안다면 링크 변경이 유리
인덱스 조회 많음순차 탐색이 필요해 불리
디버깅 핵심next와 prev 불변식을 매 작업 후 확인