[질문] 연결리스트는 추가/삭제가 O(1)임?

[3ae(3ae3ae)]

지금 공부하는 책에서 연결 리스트는 원소 추가/삭제가 O(1)이라 좋다고 하던데

연결리스트에서도 n번째 위치에 원소를 추가하려면 O(n) 시간 걸리는거 아님?

지금 n-1번째랑 n번째 원소가 누구인지를 알아야 여기에 뭘 추가하든 말든 할텐데

이 탐색이 O(n) 걸리잖아

이중 연결 리스트에서 첫 위치 / 끝 위치만 추가 삭제 O(1)로 가능한거 아님?

[익명(98.177)]

니 말이 맞음

[3ae(3ae3ae)]

ㄱㅅㄱㅅ

[익명(98.177)]

근데 linked list도 종류가 있어서 끝쪽도 포인터로 저장해두는 경우도 있고, 쌍방향으로 탐색 가능헌것도 있고 그럼

[익명(118.221)]

섹 파 구하는건 여기가 제일 쉽더라
http://eiour.com

[익명(illllllllllllll)]

o(n) 맞음 - dc App

[3ae(3ae3ae)]

ㄱㅅㄱㅅ 그럼 큐 만들 때 말고는 배열보다 나은게 없네

[익명(dish90)]

탐색을 제외하고 추가 삭제만 봤을때 O(1)이란 소리 아닐까? 배열은 추가 삭제만 놓고봐도 O(n)이잖아

[3ae(3ae3ae)]

그런거 같은데 그냥 무조건 O(1)인걸로 오해할 뻔함

[익명(118.235)]

보통 링크드리스트는 탐색을 안할때 사용함, 그리고 노드들을 배열안에 박고 링크드리스트로 이으면 인덱스로 바로 접근가능

[3ae(3ae3ae)]

근데 그럼 추가 삭제할 때 그 배열도 수정해줘야하는거 아님?

[익명(118.235)]

노드가 유효한지 안한지 따로 관리해야함 유효 안하면 그 노드 재사용해서 생성처리하고. 알고리즘 플레 다이아 문제 정도에서만 사용하긴함

[3ae(3ae3ae)]

좀 더 찾아봤는데 deque 같은거임?

[익명(220.76)]

다 사용법 따라 자료구조 쓰는건데 애초에 그냥 링크드리스트는 그걸 고려한 게 아니기 때매... 큐에서 중간 범위 접근하게 만들 순 있지만 일반적으론 선입선출부터 생각하잔어

[딱첩(ddakchup)]

넣고 뺄 위치가 주어져 있으면 O(1) 안에 삽입/삭제가 된다는 뜻으로 받아들여야 할듯. 반대로 레드 블랙 트리 같은 건 삭제하고 싶은 노드 포인터가 주어져도 노드 삭제하면서 뭔가 작업을 해줘야 되니 삭제가 O(1)에 안 되는 거고 - dc App

[익명(1.223)]

대가리나 꼬리 쳐낼때는 O(1)임

[야딩조무사(cir6174)]

그 책 뭔가 오해할 여지가 있게 쓴거같은데 - dc App

[3ae(3ae3ae)]

근데 인터넷 찾아봐도 대체로 c++ list는 추가 삭제가 O(1)이라고만 돼있던데

[야딩조무사(cir6174)]

걘 인터페이스가 이터레이터라 - dc App

[3ae(3ae3ae)]

ㄱㅅㄱㅅ 이해됨

[Knuth(392hvrv47n65)]

Inserts anywhere in a std::list are constant time operations.
That said, before you can insert, you need to get an iterator to the location you'd like to insert to, which is a linear time operation unless you're talking about the front or back.
https://stackoverflow.com/questions/3191790/stl-list-complexity

[3ae(3ae3ae)]

아 이터레이터를 찾고 나서 O(1)이라고 ㄱㅅㄱㅅ 이해됨