연결리스트

[CS - 자료구조] 배열 & 연결 리스트 (Array & Linked List)

Array 개념 연관된 data를 메모리상에 연속적, 순차적으로 미리 할당된 크기만큼 저장하는 자료구조 operation의 time plexity 조회(lookup), 마지막 인덱스에 추가(append), 삭제 : O(1) 이유 random access (즉시 접근) 설명 Array는 데이터가 연속적으로 저장되기 때문에, 한 번의 계산으로 접근 가능 삽입(insert), 삭제(delete) : O(n) 이유 Array의 연속적, 순차적인 특징 설명 데이터가 연속적, 순차적으로 붙어있어야 하기 때문에, 변경이 생긴 곳 뒤에 있는 데이터들은 일일이 자리를 밀거나 땡겨야 함 탐색(search) : O(n) 이유 주소값 하나씩 돌면서 찾는 데이터가 어떤 주소값에 있는지 일일이 확인해야 함 장점 조회(lookup..