자바에서 arraylist랑 linkedlist 차이점이 전자는 탐색이 O(1)인 반면 삽입/삭제가 O(n)이고 후자는 탐색이 O(n)에 삽입/삭제가 O(1)이라는데
여기서 왜 linkedlist 삽입 삭제가 O(1)인지 이해가 안 감.
직관적으로 생각해서 삽입 삭제하는 부분 앞뒤로 링크 잘라붙이면 될 거 같은데
중간 노드 참조하려면 head나 tail에서 시작해서 원하는 노드까지 도달해야되는 걸로 알고 있는데 삽입 삭제도 마찬가지 아님?
노드 100개 있을 때 이름이 홍길동인 노드 삭제하려고 할 때 얘가 예를 들어 50번째에 있는 애면 1번부터 50번까지 홍길동 있나 찾고 발견하면 그제서야 지울 수 있는 거 아님?
왜 linkedlist가 삽입 삭제에 유리하다고 하는지 설명좀 본인은 공부중인 대학생임
여기서 왜 linkedlist 삽입 삭제가 O(1)인지 이해가 안 감.
직관적으로 생각해서 삽입 삭제하는 부분 앞뒤로 링크 잘라붙이면 될 거 같은데
중간 노드 참조하려면 head나 tail에서 시작해서 원하는 노드까지 도달해야되는 걸로 알고 있는데 삽입 삭제도 마찬가지 아님?
노드 100개 있을 때 이름이 홍길동인 노드 삭제하려고 할 때 얘가 예를 들어 50번째에 있는 애면 1번부터 50번까지 홍길동 있나 찾고 발견하면 그제서야 지울 수 있는 거 아님?
왜 linkedlist가 삽입 삭제에 유리하다고 하는지 설명좀 본인은 공부중인 대학생임
니말이 맞아. 그래서 보통은 o(n)이라고 하는데. 탐색을 제외한다면 o(1)이겠지 아니면 이중연결리스트거나
ArrayList는 삭제 연산 수행 후, 삭제 대상 인덱스 뒤에서부터 한 칸씩 앞으로 당겨줘야함. [1],[2],[3],[4],[5] 에서 2번 째 인덱스 [3]삭제 -> [1],[2],[null],[4],[5] -> 타겟 인덱스 뒤에서 부터 한 칸 씩 앞으로 이동 연산 수행 -> [1],[2],[4],[5] LinkedList는 삭제 연산 대상이 되는 노드의 앞 뒤 연결만 바꿔주면 됨 (삭제 대상 인덱스 전 후로 인덱스를 움직이는 연산이 필요 x) 탐색 연산 생각말고 삭제 연산만 생각해보셈
ArrayList에서 삭제 후 전체 인덱스를 조정하는 연산 때문에 , LinkedList에 비해 연산이 느리다는거임
탐색다 돼서 노드 찾았고, 그 상태에서 삽입/삭제하려고 할 때 O(1)
ArrayList도 삽입, 삭제할 때 대상을 찾으려면 탐색 해야 할거아니냐, 그부분은 둘 다 같은 시간이 걸리겠지, 그걸 제외하고 보자 이거 아닌가?
ArrayList는 배열을 사용하여 데이터를 저장합니다. 배열은 연속적인 메모리 공간에 저장되기 때문에 탐색은 O(1)입니다. 하지만 삽입이나 삭제는 배열의 크기를 조정해야 하기 때문에 O(n)입니다. LinkedList는 노드로 연결된 데이터 구조입니다. 노드에는 데이터와 다음 노드에 대한 포인터가 있습니다. LinkedList는 삽입이나 삭제가 O(1)인 이유는 노드를 연결하는 포인터를 변경하기만 하면 되기 때문입니다.