현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

단순링크드를 이용한 스택 구현에서....

shs0917의 이미지
글쓴이: shs0917 / 작성시간: 월, 2004/04/12 - 9:39오전

Quote:

...........................................Top
.............................................|
[Header] -> [Node1] -> [Node2] -> NULL
----------------------------------> 추가 방향

이렇게 구현할 경우.. delete를 할 수 없지 않나요? 단방향 링크드에서는
자신의 앞에 있는 노드의 주소를 알 수 없잖아요.. 그래서
Quote:

Top
|
[Node2] -> [Node1] -> [Header] -> NULL
<--------------------------------추가 방향

그래서 이런식으로 거꾸로 노드를 추가하면 해결된다고 하던데요..
그런데.. 단방향 링크드에서 이런 식으로 추가한다는것 자체가 오류가 있는거
아닌가요? 제가 아직 동적 링크드리스트를 제대로 이해를 못한건지.
가르침 부탁 드립니다.
Forums: 
프로그래밍 QnA
sozu의 이미지

글쓴이: sozu / 작성시간: 월, 2004/04/12 - 9:43오전

shs0917 wrote:
Quote:

Top
|
[Header] -> [Node1] -> [Node2] -> NULL
----------------------------------> 추가 방향

이렇게 구현할 경우.. delete를 할 수 없지 않나요? 단방향 링크드에서는
자신의 앞에 있는 노드의 주소를 알 수 없잖아요.. 그래서

앞에 있는 노드의 주소를 저장하면서 노드를 따라 내려가면 됩니다^^

그리고 지울 노드를 마주치게 되면 앞의 노드의 주소를 저장하고 있기 때문에

안전하게 지울수 있겠죠 :D

-----------
청하가 제안하는 소프트웨어 엔지니어로써 재미있게 사는 법
http://sozu.tistory.com

alsong의 이미지

글쓴이: alsong / 작성시간: 월, 2004/04/12 - 9:54오전

Quote:
[Node2] -> [Node1] -> [Header] -> NULL

header가 변합니다. 즉, header는 따로 가지고 있어야 됩니다.
마지막에 insert된 element가 header가 됩니다.
insert될 element가 있을때

link header;

link newelement;
newelement->next = header;
header = newelement;

delete될 때

tmp = header;
header = header->next;
free(tmp);

그나저나 백수 언제 탈출하냐... ㅡㅡ; 배고파라.

shs0917의 이미지

글쓴이: shs0917 / 작성시간: 월, 2004/04/12 - 9:56오전

결국엔 top 이외의 node_ptr가 하나 더 필요하다는 말이 되겠군요..ㅡㅡㅋ
그렇다면 node마다 주소를 다 알아야 할텐데.. node_ptr형의 배열이
필요하게 되는거 아닐까요?? 그렇다면 차라리 top을 node_ptr 배열로
선언해버리면 되지 않을까요? 그리고.. 그렇게 되면 최대 사이즈가
node_ptr의 갯수만큼 제한이 되기 때문에.. 크기 제한이 없는 스택을
만드는데 문제가 되지 않을까요?? 제가 워낙 실력이 없어서.. 어이없는
질문을 하는건지도 모르겠네요. 이해해주세요..

컴퓨터가 이해할수 있는 코드는 어느 바보나 다 작성할 수 있다. 좋은 프로그래머는 사람이 이해할 수 있는 코드를 짠다 - 마틴파울러

Seven..의 이미지

글쓴이: Seven.. / 작성시간: 월, 2004/04/12 - 9:56오전

Quote:
그래서 이런식으로 거꾸로 노드를 추가하면 해결된다고 하던데요..
그런데.. 단방향 링크드에서 이런 식으로 추가한다는것 자체가 오류가 있는거

그렇죠^^ 그럼 더블 링크드 리스트가 되어버리니까.
윗분 말씀처럼 하나의 변수를 추가해서
따라 내려가면서 이전 노드의 주소를 기억만 한다면;
지우는데 깔끔하게 지울 수 있겠죠^^

VENI VIDI VICI

alsong의 이미지

글쓴이: alsong / 작성시간: 월, 2004/04/12 - 9:57오전

top만 있으면 됩니다.

그나저나 백수 언제 탈출하냐... ㅡㅡ; 배고파라.

shs0917의 이미지

글쓴이: shs0917 / 작성시간: 월, 2004/04/12 - 10:37오전

링크드리스트에서 헤더는 절대로 변하면 안된다는 식으로
들은것 같은데.. 답변 보니까.. 헤더가 변한다고 하셨더라구요..
계속해서 미궁속으로 빠져드는 기분입니다.. :oops:

컴퓨터가 이해할수 있는 코드는 어느 바보나 다 작성할 수 있다. 좋은 프로그래머는 사람이 이해할 수 있는 코드를 짠다 - 마틴파울러

bugiii의 이미지

글쓴이: bugiii / 작성시간: 월, 2004/04/12 - 10:48오전

top or head 말고 tail 이라고 생각해보시면 더 간단합니다.

새로 추가되는 것이 이전 마지막을 가리키게 되고 새로 추가되는 것이 새로운 마지막이 되는 것이겠죠.

그 스택에서 뭘 꺼내 올 때 top or tail 이라고 하는 것이 NULL 이면 비어 있는 것이 되고요...

첫 그림의 화살표 방향을 거꾸로 뒤집어서 생각하시면 됩니다... 그리고 NULL의 위치도 마지막이 아니라 처음으로 바뀌구요...

스택이라고 하셨으니 현재의 마지막만 알면 되니까요. 다른 것은 불필요한 낭비입니다.

보통 간단한 (메모리) 풀을 이런식으로 하는 경우가 종종 있습니다. 이렇게 되면 항상 마지막에 사용했던 것을 다시 사용하는 것이 되겠습니다.

p.s. 앞으로 2개만 더 쓰면 300개 달성!!!

shs0917의 이미지

글쓴이: shs0917 / 작성시간: 월, 2004/04/12 - 10:50오전

관심 가져주신 모든 분들께 감사드립니다... 처음부터 다시 구현해봐야
겠네요... 정말 많은 도움 되었습니다. :lol:

컴퓨터가 이해할수 있는 코드는 어느 바보나 다 작성할 수 있다. 좋은 프로그래머는 사람이 이해할 수 있는 코드를 짠다 - 마틴파울러

sozu의 이미지

글쓴이: sozu / 작성시간: 월, 2004/04/12 - 10:51오전

그렇죠.

사실, Top만 알면됩니다.

Pop, Push는 Top에서만 일어나니...사실 아래로 내려가서 중간것을 지울일은 없을겁니다. :D

그리고 위에분이 말씀하신것처럼

Locality를 증가시키기 위해 Memory Pool 이나 Thread Pool을

스택을 이용해서 구현하는 경우가 많죠 :D

-----------
청하가 제안하는 소프트웨어 엔지니어로써 재미있게 사는 법
http://sozu.tistory.com

shs0917의 이미지

글쓴이: shs0917 / 작성시간: 월, 2004/04/12 - 3:04오후

단방향 링크드 리스트에서 결론을 나름대로 지었습니다.

NULL<-[Header]<-[Node1]<-[Node2]
------------추가 방향-------------->top

temp를 이용해서 이러한 식으로 하니까 별 문제가 없네요..
도움 주신 모든 분들께 감사드립니다.

컴퓨터가 이해할수 있는 코드는 어느 바보나 다 작성할 수 있다. 좋은 프로그래머는 사람이 이해할 수 있는 코드를 짠다 - 마틴파울러

bugiii의 이미지

글쓴이: bugiii / 작성시간: 월, 2004/04/12 - 3:13오후

Header 라는 것도 필요없습니다. 마지막은 top 이 NULL 을 가리키는지를 판단하면 됩니다.

shs0917의 이미지

글쓴이: shs0917 / 작성시간: 월, 2004/04/12 - 3:30오후

아.. 그런것이었군요.. 감사합니다..

컴퓨터가 이해할수 있는 코드는 어느 바보나 다 작성할 수 있다. 좋은 프로그래머는 사람이 이해할 수 있는 코드를 짠다 - 마틴파울러

댓글 달기

텍스트 포맷에 대한 자세한 정보

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.