자료구조 1 Page 노트 정리_Linked List 연결 리스트

 

연결 리스트 (Linked List)

- 데이터를 링크로 연결해서 관리하는 자료구조
- 자료의 순서는 정해져 있지만 메모리상 연속성이 보장되지는 않음
- 장점: 데이터 공간을 미리 할당할 필요 없음(데이터 길이 가변적이어서 데이처 추가/삭제 용이)
- 단점: 연결구조를 위한 별도 데이터 공간 필요, 연결 정보 찾는 시간 필요(접근 속도 상대적으로 느림), 데이터 추가/삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요
- 노드(node): 데이터 저장 단위로 값과 포인터로 구성
- 데이터 추가/삭제: 위치(head/중간/tail)에 따른 연결 작업 필요

List 구현체

- Array list: 배열(array)을 사용하여 list를 구현
- Linked list: 노드를 연결(linked) 시키는 형태로 구현