c로 구현한 알고리즘 보다가 이해가 되지 않는 점이 있습니다.

익명 사용자의 이미지

초보자가 공부도중에 이해가 되지 않는점이 있어
선배님들께 질문을 해봅니다.

공부중인 책은 c로 구현한 알고리즘 (http://www.hanbit.co.kr/store/books/look.php?p_code=B6520175751)입니다.

리스트 항목의 구조체는 아래와 같습니다.

typedef struct ListElmt_ {
	void *data;
	struct ListElmt_ *next;
} ListElmt;

주어진 함수는 단일 리스트에서
주어진 element의 다음element를 삭제하는 함수를 구현하였고
왜 해당 element가 아니라 다음 element를 삭제 하는게 좋은지
적은 내용입니다.

함수는 ListRemove_Next(List *list, ListElmt *element_Remove, void **data) 이런식으로 되어 있습니다.

이해가 되지 않는 부분은 노란색 박스에 있는 부작용에 대한 부분입니다.
제 생각으로는 정상적으로 작동할것이라고 생각됩니다만...
부작용이라서 아니라고 하네요.

무엇이 문제일까요?

감사합니다.

File attachments: 
첨부파일 크기
Image icon 20170504_160428.jpg606.85 KB
질문자의 이미지

앗 첨부파일이 자동으로 보여지지 않네요.
클릭하셔서 읽어주시면 감사하겠습니다.

세벌의 이미지

성의 없는 질문에 답변을 기대하지 마세요.
노란색 박스 안에 있는 내용을 질문하신 분께서 직접 쳐서 본문에 나타나게 해 주셔요.

chadr의 이미지

노란색 박스를 본문에 적어주셨으면 좋겠는데, 담부터는 적어주세요.
리스트에서 원소를 삭제하기위해서는 해당원소의 이전원소의 주소가 필요합니다. 그런데 단방향리스트에서는 이전원소의 주소를 알수없으니 얻으려면 리스트 처음부터 찾아야하죠. 책에서 말하는 방식으로 next를 삭제하게되면 next의 이전 원소는 함수에 입력하는 원소의 주소가되므로 이전 원소 주소는 알고있는것이고 next주소는 당연히 입력하는 원소의 next필드에서 얻어올수 있으므로 탐색시간이 상수시간으로 처리가능하기 때문에 next를 삭제하는 방식이 아닌 방법은 비효율적이라는 것입니다.

-------------------------------------------------------------------------------
It's better to appear stupid and ask question than to be silent and remain stupid.

raymundo의 이미지

질문 방식은 확실히 답변자를 불편하게 만드는 식입니다만, 내용이 유익하고 재미있어서 퉁치는 걸로 하고...
저 노란 박스 안의 말의 취지는 짐작이 되는데, 제가 보기에는 약간 오역이 있어서 더 헷갈리는 것 같습니다.

예를 들어 1 -> 2 -> 3 -> 4 -> 5 이 리스트에서 3을 지우고 1 -> 2 -> 4 -> 5 를 만들고 싶은데,

1) 3노드를 가리키는 포인터를 인자로 주어서 3노드를 삭제할 수는 없음. 왜냐하면 2노드의 next 필드를 변경해야 하는데 3노드에서 2노드를 찾아갈 수 없으니까.

2) 그렇다고 헤드에서부터 시작해서 계속 이전 노드 포인터를 관리하면서 3을 찾아낸 다음 2노드의 next를 변경하자니 이건 복잡도가 O(n)이 되어 버림

3) 이제 문제의 방법인데, 3노드 포인터를 인자로 받아 그 노드에 다음 노드의 데이터인 4를 복사한 후 이 3노드(이제는 4이지만)의 next가 5노드를 가리키게 하고 기존 4노드를 제거하면 1->2->4->5가 됨.

이 방법이 그럴싸해보이지만, 만일 기존4노드를 따로 가리키고 있던 외부의 포인터 변수가 있었다면, 이 변수는 하루아침에 자신이 가리키던 노드가 free되어 버린 봉변을 당하게 된다는 얘기입니다. 물론 이건 링크드 리스트의 어떤 노드를 삭제하든 똑같이 발생할 수 있는 문제이긴 하겠습니다만, '내가 지우려는 노드가 지워져서 어쩔 수 없이 생기는 경우'와 '지우려는 노드는 이 노드인데 엉뚱하게 저 노드를 가리키던 포인터가 봉변을 당하는 경우'의 차이라고 보는 것 같네요.

However, this seemingly benign O (1) approach generates the dangerous side effect of rendering a pointer into the list invalid. This could be a surprise to a developer maintaining a pointer to the element after the one thought to be removed!

into를 보니 리스트 외부에서 내부를 가리키는 포인터를 말하는 것 같고, 역자분은 maintaining... 이 주어인데 길어서 뒤로 보내고 this 로 치환한 거라고 해석을 하셨나본데, 제 생각에는 그냥 바로 앞의 developer를 수식하는 말 같습니다. "이러면 삭제된 줄 알았던 원소의 다음 원소를 가리키는 포인터를 관리하고 있던 개발자가 놀라게 될 것이다"

뭐 제가 완전히 잘못 짚은 것일 수도 있고요.

좋은 하루 되세요!

 의 이미지

약간의 오역 정도가 아니로군요.

이런 종류의 오역이 속출한다면 그런 번역서는 피하는 게 좋습니다.
영어 원서를 못 보시겠다면 차라리 한국인 저자가 한국어로 쓴 책을 찾아보세요.

jick의 이미지

훌륭한 답변으로 보입니다만, 사족을 달자면 위의 문장에서 maintain은 "관리하다"가 아니라 그냥 "들고 있다" (내지는 "갖고 있다")로 해석하는 것이 나을 것 같습니다.

* maintain은 꼭 "관리한다"라는 뜻이 아니고 뭔가를 지속적으로 계속 가지고 있는 경우에도 쓰입니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.