[자료구조-3] 선형 리스트(ArrayList), 연결 리스트(LinkedList)

선형 리스트(ArrayList) 데이터를 순서대로 나열해 놓은 자료 구조 메모리에 연속으로 할당되기에 접근 속도가 매우 빠르다. 데이터 삽입, 삭제 시 데이터의 이동이 필요하기에 작업에 소요되는 시간이 길다. 연결 리스트 데이터를 연속적으로 배치시키지 않고 각 자료마다 노드의 포인터 부분을 이용하여 연결시킨 자료 구조 데이터 삽입, 삭제 시 매우 빠르게 처리가 가능하다. 포인터를 찾는 시간이 필요하여 데이터 접근 속도가 느리다. 선형 리스트와 연결 리스트 시간 복잡도 search add remove ArrayList O(1) O(n) O(n) LinkedList O(n) O(1) :맨 앞, 맨 뒤 O(n) : 중간 삽입 O(1) :맨 앞, 맨 뒤 O(n) : 중간 삽입