연결 리스트 삽입과 삭제 질문드립니다.
1분 50초 가량에 배열에서 데이터를 추가하려는 경우 overhead가 많이 발생하는데
연결 리스트의 경우 중간에 데이터를 삽입하면 다음을 가리키는 노드만 바꿔주면 되기 때문에
간단한 작업이라고 나와 있습니다.(데이터의 삭제도 마찬가지)
---------------------------------------------------------------------------------------
하지만 4분 9초 가량에 배열과 연결리스트의 삽입과 삭제를 비교하실 때
배열은 위의 얘기와 동일한 말씀을 하셨는데( O(n)의 성능을 가진다. )
연결리스트에서 "삽입하려는 노드까지 노드를 계속 타고 가야하기 때문에 O(n)의 성능을 가진다."
라고 하셨는데 이 말씀은 "중간에 데이터를 삽입하면 다음을 가리키는 노드만 바꿔주면 되기 때문에 간단한 작업"
이 말과 충돌한다고 생각합니다.
---------------------------------------------------------------------------------------
"삽입하려는 노드까지 노드를 계속 타고 가야하기 때문에 O(n)의 성능을 가진다."
이 말은 데이터 참조에 해당하는 말이 아닌지 질문 드리고 싶습니다.
---------------------------------------------------------------------------------------
결국에 제 말이 틀린거라면
즉, 연결리스트도 삽입과 삭제 시 O(n)의 성능을 가진다면 배열과 비교했을 때 연결리스트의 유일한 장점은
처음에 크기를 지정해 주지 않아도 된다는 점 하나 뿐인 것인가요?
Answer 1
0
정확히는 연결리스트는 처음과 끝의 데이터의 삽입, 삭제가 O(1)이고 중간에 삽입하는 건 O(n)입니다.
중간에 데이터를 삽입하는 경우 원하는 인덱스까지 참조해야하기 때문이죠.
C언어에서 배열은 메모리에 연속적으로 위치하고 연결리스트는 떨어져 있는 메모리를 사용할 수 있다는 것이 장점이 있습니다.
그리고 "중간에 데이터를 삽입하면 다음을 가리키는 노드만 바꿔주면 되기 때문에 간단한 작업"
이 말은 C언어에서 배열이 메모리에 연속적으로 할당되기 때문에 중간에 데이터를 삽입하게 되면 뒤에 있는 데이터를 모두 이동시켜야하는 복잡한 과정이 필요하지만 연결리스트는 다음 노드를 가리키는 것(포인터)만 바꿔주기 때문에 굉장히 간단합니다. 원하는 인덱스를 찾는 건 당연히 O(n)이고 여기서 삽입하는 과정이 간단하다는 말입니다.
자바스크립트에서 배열은 전통적인 배열과는 다르게 크기도 런타임에 수정가능합니다.
따라서 연결리스트와 큰 차이를 느끼긴 힘들겠지만 일반적인 배열과 연결리스트의 차이점만 알아두시면 될 것 같습니다.
자바스크립트의 배열에 대해서 궁금하시면 이 게시물을 참조해주세요!
큐의 마지막 데이터가 head에 위치해야 하는 이유가 궁금합니다.
0
71
2
이중연결 리스트 데이터 삭제시 질문이 있습니다.
1
60
2
자바스크립트 배열은 동적이 아닌가요?
1
85
2
자바스크립트 배열
0
75
2
코테에서 링크리스트 자료구조를 사용해야 하면, 이번 강의에서 구현한 메서드들도 모두 직접 구현하면 되나요?/
0
148
2
공부 방식 질문 드립니다.
1
115
2
메모이제이션과 타뷸레이션 관련해서 질문드립니다.
1
166
2
병합정렬에서 질문이 있습니다.
2
140
1
병합정렬 질문 있습니다.
1
136
5
데이터 삽입, 삭제 함수 오류 범위 설정
0
156
2
해시 테이블에서 질문이 잇습니다.
2
126
2
시간복잡도 계산 시 1회 연산당 연산량은 왜 고려하지 않는 건가요?
1
146
2
터미널 설정
0
112
2
2:13분 관련 질문입니다
0
89
1
8:47초경부터 9:00초까지 질문입니다.
1
132
2
tail을 삭제하는 경우에 관련해서 질문이 있습니다.
0
106
1
2:36초 head 위치가?
1
108
2
환경구축강의 중 터미널 파일 실행오류
0
159
2
4:58 이중for문 질문있습니다.
0
103
1
hanoi함수 처음 호출에 대해서 여쭤봅니다.
1
127
2
해쉬테이블 데이터 관련해서 질문있습니다.
0
145
2
자바스크립트 Map과 어떤 차이가 있나요??
0
201
2
질문이있습니다.
0
101
1
2번째 복습 스터디📖 를 진행하고 스터디원분들과 나눈 질문들 입니다.(자료구조와 알고리즘)
1
144
2