배열 & 연결 리스트 (Array & LinkedList)

배열 (Array)

-정적 자료구조
연속된 메모리 주소를 할당 받고 있기 때문에 데이터가 인덱스(index)라는 것을 갖게 됨

index를 갖게 된다는 것은 즉 임의 접근이 가능
그러므로 접근과 탐색에 용이합니다.

하지만 크기를 미리 정해놓았기 때문에 수정하는 것이 불가능
또한 이미 크기를 정해 놓은 터라 해당 배열 크기 이상의 데이터를 저장할 수 없다

연결 리스트(LinkedList)

동적 자료구조
크기를 정할 필요가 없rh, 배열처럼 연속된 메모리 주소를 할당 받지 않음

대신 노드(Node)라는 게 존재하며, 그 노드 안에 데이터가 있고, 다음 데이터를 가리키는 주소를 가지고 있다.

연결 리스트는 위에서 말한 것처럼 크기를 정해 놓지 않았기 때문에 크기의 제한이 없다. 그로 인해 데이터 추가, 삭제가 자유롭다는 장점이 있습니다.

반면에 배열처럼 연속적인 메모리 주소를 할당 받지 않았기 때문에 임의로 접근하는 것이 불가능합니다. 그 말은 즉슨 데이터를 탐색할 때 순차적으로 접근해야 한다

시간복잡도

배열은 index를 가지고 있기 때문에 탐색은 O(1)의 시간복잡도를 가집니다.

삽입의 경우는 맨 뒤라고 한다면 O(1)의 시간복잡도를 가지지만 맨 뒤가 아닌 나머지는 O(n)이다.

연결 리스트는 추가, 삭제가 용이하다고 했죠. 삽입은 맨 앞일 경우 O(1)의 시간복잡도, 맨 앞이 아닌 나머지는 O(n)입니다.

그리고 배열과 반대로 탐색은 O(n)의 시간복잡도를 가집니다.