-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
연결 리스트 삽입과 삭제 질문드립니다.
23.01.24 00:01 작성 조회수 524
1
1분 50초 가량에 배열에서 데이터를 추가하려는 경우 overhead가 많이 발생하는데
연결 리스트의 경우 중간에 데이터를 삽입하면 다음을 가리키는 노드만 바꿔주면 되기 때문에
간단한 작업이라고 나와 있습니다.(데이터의 삭제도 마찬가지)
---------------------------------------------------------------------------------------
하지만 4분 9초 가량에 배열과 연결리스트의 삽입과 삭제를 비교하실 때
배열은 위의 얘기와 동일한 말씀을 하셨는데( O(n)의 성능을 가진다. )
연결리스트에서 "삽입하려는 노드까지 노드를 계속 타고 가야하기 때문에 O(n)의 성능을 가진다."
라고 하셨는데 이 말씀은 "중간에 데이터를 삽입하면 다음을 가리키는 노드만 바꿔주면 되기 때문에 간단한 작업"
이 말과 충돌한다고 생각합니다.
---------------------------------------------------------------------------------------
"삽입하려는 노드까지 노드를 계속 타고 가야하기 때문에 O(n)의 성능을 가진다."
이 말은 데이터 참조에 해당하는 말이 아닌지 질문 드리고 싶습니다.
---------------------------------------------------------------------------------------
결국에 제 말이 틀린거라면
즉, 연결리스트도 삽입과 삭제 시 O(n)의 성능을 가진다면 배열과 비교했을 때 연결리스트의 유일한 장점은
처음에 크기를 지정해 주지 않아도 된다는 점 하나 뿐인 것인가요?
답변을 작성해보세요.
0
감자
지식공유자2023.01.24
정확히는 연결리스트는 처음과 끝의 데이터의 삽입, 삭제가 O(1)이고 중간에 삽입하는 건 O(n)입니다.
중간에 데이터를 삽입하는 경우 원하는 인덱스까지 참조해야하기 때문이죠.
C언어에서 배열은 메모리에 연속적으로 위치하고 연결리스트는 떨어져 있는 메모리를 사용할 수 있다는 것이 장점이 있습니다.
그리고 "중간에 데이터를 삽입하면 다음을 가리키는 노드만 바꿔주면 되기 때문에 간단한 작업"
이 말은 C언어에서 배열이 메모리에 연속적으로 할당되기 때문에 중간에 데이터를 삽입하게 되면 뒤에 있는 데이터를 모두 이동시켜야하는 복잡한 과정이 필요하지만 연결리스트는 다음 노드를 가리키는 것(포인터)만 바꿔주기 때문에 굉장히 간단합니다. 원하는 인덱스를 찾는 건 당연히 O(n)이고 여기서 삽입하는 과정이 간단하다는 말입니다.
자바스크립트에서 배열은 전통적인 배열과는 다르게 크기도 런타임에 수정가능합니다.
따라서 연결리스트와 큰 차이를 느끼긴 힘들겠지만 일반적인 배열과 연결리스트의 차이점만 알아두시면 될 것 같습니다.
자바스크립트의 배열에 대해서 궁금하시면 이 게시물을 참조해주세요!
답변 1