완전 초짠데요 싱글리링크드리스트 질문입니다.

[익명(218.235)]

단일 리스트에서 테일의 삭제가 느린건 알겠는데요 테일의 삽입은 빠르다는 것을 이해하지 못하겠어서 질문 올립니다.

답변해주시면 감사하겠습니당

[20160525(circir6174)]

테일 삽입이라는게 0->0->0->0->(삽입) 이게 빠르다는거?

[20160525(circir6174)]

그거 졸라느림 헤드에 붙이는거 말하는거같은데

[익명(218.235)]

수업시간에 배우기를 테일에서의 삭제는 비효율 적이지만 테일에서의 삽입은 그렇게 비효율적이지 않다고 설명하셨는데 쪽팔려서 못물어봤음여

[20160525(circir6174)]

무슨말인지 알겠음

[제페(zepeh)]

List는 삽입, 삭제에 별달리 느린 게 없을텐데..? c++에서의 벡터도 아니고.. 벡터는 앞단 삽입/삭제가 느림

[20160525(circir6174)]

그건 따로 tail의 포인터를 갖고있어서 그런거임 tail포인터가 있으면 뒤에 붙일때 그냥 tail포인터 참조해서 끝부분에 간다음 붙이면 되는데 삭제하면 tail포인터를 다시 찾아줘야하는데 거기서 비효율이 발생함

[20160525(circir6174)]

싱글리스트고 어디가 헤드, 테일인지도 알고있는 상황임 그냥 단일연결리스트만 있는게 아니라

[제페(zepeh)]

리스트는 앞단 추가, 뒷단 추가, 중간 추가 모두 준수함 벡터는 앞단이나 중간 삽입이 일어나려면 기존 요소들을 밀어내는 작업을 해줘야 하기 때문에 느리고.

[ㅈㄱ(39.120)]

테일삭제는 널값나올때까지 달리는거라 비효율?

[20160525(circir6174)]

ㅇㅋ 맞음

[제페(zepeh)]

음 단일이면 그럴 수 있겠네 tail일 경우 tail 노드에서 이전 요소는 알 순 없으니

[20160525(circir6174)]

삭제 자체는 비용이 크지않는데 삭제한다음 어디가 테일인지 표시하는게 비쌈

[익명(218.235)]

아 설명 감사합니다. 근데 제가 진짜 초보라서 그런데 삭제도 삽입할때처럼 테일포인터 참조해서 삭제하면 그만아닌가요?

[whatugonnado(sibal214)]

tail 포인터 하나만 만들어놔도 안느린데

[20160525(circir6174)]

삭제하는건 안비싼데 삭제하면 tail이 갱신될거아님 그거 갱신할때는 다시 처음부터 끝까지 달려야함

[익명(218.235)]

확실히 이해됐습니다 감사합니다