열혈 자료구조를 다시 읽으며 공부하면서 정리하는 내용

Linked List

특징

• 순차적으로 저장
• 중복저장 허용

종류

• 순차리스트 : 배열기반
• 연결리스트 : 메모리 동적할당 기반

* 리스트의 특징을 구현하기위해 배열/메모리동적할당 기반으로 만든것.(반대라고 착각하면 안됨!)

순차연결리스트

장점

• 데이터 참조 용이(인덱스값으로 한번에 접근가능)

단점

• 크기 초기 결정, 변경불가
• 삭제과정 중 데이터 이동 많음(비효율)

위의 단점을 해결하기 위해 동적할당을 활용

→ 연결리스트

data 생성시 마다 동적할당하고 연결(순차접근이 가능하게 하기위해)
Node(각 네모)는 data와 link로 구성됨

노드 추가 위치

• head

  tail 필요 없음 / 저장 순서 유지 안됨

• tail

  저장 순서 유지 / tail 필요함

cf. 데이터 삭제시,
지울 노드 먼저 삭제하면 안됨!
왜냐하면 연결이 끊어지면 뒤에 데이터에 접근할 수 없기 때문에.
꼭 연결을 마친 후 지울 것