[1028알고리즘 08]배열 vs 링크드리스트

	배열	링크드리스트특징 배열 링크드리스트
정의	같은 종류의 데이터들이 순차적으로 저장되는 자료구조	각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다
특정원소 조회	원소에 즉시 접근 0부터 시작하는 인덱스 존재O(1)	리스트 특정원소 접근시 연결고리를 따라 탐색 O(N)
원소를 삽입/삭제	O(n)	O(1)의 시간복잡도 앞뒤 포인터만 변경
원소 새로 추가	모든 공간 다 차면 새로운 공간 할당	모든 공간 다 차도 맨 뒤에 노드만 동적추가
특징	크기가 정해진 데이터 공간, 변경 불가,데이터 접근하는 경우가 빈번하면 Array	리스트는 크기가 정해지지 않은 데이터 공간삽입 삭제 빈번하면 LinkedList

python 배열은 list 라고 부름 append 를 함 >> 파이썬 list는 array 로 구현

append시 내부적으로 동적배열을 사용하여 배열의 길이가 늘어나도 O(1) 시간복잡도 되도록 설계

파이썬의 경우 배열은 링크드리스트로 쓸수 있고, 배열로도 쓸수있게 만든 효율적 자료구조

 

링크드 리스트 구현