linkedlist1

• Array vs Linked List Array 논리적 저장 순서와 물리적 저장 순서가 일치.(index를 활용하여 해당 element에 접근 할 수 있다.) 해당 원소에 인덱스를 알고 있으면 O(1)이라는 시간 복잡도를 갖는다. Random Access가 가능하다. 하지만 삭제 또는 삽입과정에서 비용이 많이 발생한다. 해당 원소의 삽입 과정에서 맨 뒤의 경우를 제외하고 원소들이 있는 처음 또는 중간에 넣게 된다면 삽입할 공간을 만들기 위해 해당 원소들이 뒤로 이동해야하는 비용이 발생한다. 해당 원소의 삭제 과정에서 해당 원소를 삭제 한 후 빈 공간이 생긴다. 이 빈 공간을 매우기 위해 빈 공간 다음으로 이어지는 원소들을 한 칸씩 앞으로 떙겨야 하므로 비용이 발생한다. 비용에 대한 시간 복잡도는 O(n) 이다. Linked List 배열에 .. CS/DataStructure 2021. 3. 30.