Index로 빠르게 값을 찾는 것이 가능
데이터의 삽입 및 삭제가 빠름
데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림
우선 배열은 선언할 때 크기와 데이터 타입을 지정해야 합니다.
따라서 데이터가 계속 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용하기에 부적합합니다.또한 중간에 데이터를 삽입하거나 삭제할때도 매우 비효율적입니다.
대신, 배열을 사용하면 index가 존재하기 때문에 위치를 바로 알 수 있어 검색에 편한 장점이 있습니다.
이를 해결하기 위해 나온 것이 List입니다.
List는 array처럼 크기를 정해주지 않아도 됩니다. 대신 array에서 index가 중요했다면, List에서는 순서가 중요합니다.
크기가 정해져있지 않기 때문에, 중간에 데이터를 추가하거나 삭제하더라도 array에서 갖고 있던 문제점을 해결 가능합니다. index를 가지고 있으므로 검색도 빠르다.
하지만, 중간에 데이터를 추가 및 삭제할 때 시간이 오래걸리는 단점이 존재합니다.
Linked List는 종류가 무엇이든, 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식으로 되어있습니다.
이런 방식을 활용하면서, 데이터의 중간에 삽입 및 삭제를 하더라도 전체를 돌지 않아도 이전 값과 다음값이 가르켰던 주소값만 수정하여 연결시켜주면 되기 때문에 빠르게 진행할 수 있다.
이렇게만 보면 가장 좋은 방법 같아보이지만, List의 k번째 값을 찾아라에서는 비효율적입니다.