안녕하세요 연결리스트에 대해 몇가지 질문드립니다.

thenongbu1의 이미지

이 글을 클릭해주셔서 감사합니다.

몇가지 질문드립니다. 답변해주시면 정말 감사하겠습니다.

1. 이중 연결리스트의 장점은 역시 양방향 순회일텐데요,

양방향 순회를 굳이 왜 해야 하는 건지 좀 이해가 안되네요... 단방향이나 양방향이나 대체 무슨 차이가 있는 건지도 납득이 안가네요. 어떤 때 양방향 순회를 해야하는지, 효과적인지 알 수 있을까요?

그리고 저는 애초에 연결리스트를 사용할 때는 데이터 검색이 필요없는 상황이어야 쓸 수 있을 거 같은데 제 생각이 맞을까요?

2. 배열로 이루어진 리스트와 연결리스트의 차이점은 역시 삽입 삭제일텐데, 어느 정도의 빈도로 삽입, 삭제가 이루어져야 배열리스트가 연결리스트보다 유리해질 수 있는지 혹시 공식같은게 있을까요?
그리고 삽입 삭제가 배열리스트보다 연결리스트가 유리한건 알겠는데 힙에 메모리를 할당하기 때문에 메모리 단편화 이슈에서 자유로울 수 없을 거 같은데 고수분들은 어떻게 생각하시는지 궁금합니다.

자료구조는 구현해보려면 간단하지만 생각을 깊게 할 수록 어렵네요...
끝까지 글을 읽어주셔서 감사합니다.

swish95의 이미지

그걸 고민하는게 설계죠
정석적인 계산 방법이야 빅 O 를 쓰면 되겠지만 케바케니..

------------------------------------------------------------
ProgrammingHolic

라스코니의 이미지

1. 실제로 매우 단순한 목적이 아니면 single linked list로는 충분하지 않습니다. 예를들어 어떤 아이템을 삭제를 했는데 바로 이전의 아이템을 접근할 필요가 있을 때 doubly linked list에서는 바로 prev 항목을 들여다 보면 되지만, single linked list에서는 처음부터 다시 검색해 나가야 됩니다.

2. 배열로 이루어진 리스트와 연결리스트의 차이점은 역시 삽입 삭제일텐데, 어느 정도의 빈도로 삽입, 삭제가 이루어져야 배열리스트가 연결리스트보다 유리해질 수 있는지 혹시 공식같은게 있을까요? ==> 흥미로운 주제로 보이는데 구글 검색을 하면 아마 관련 연구가 꽤 되어있을 겁니다.

그리고 삽입 삭제가 배열리스트보다 연결리스트가 유리한건 알겠는데 힙에 메모리를 할당하기 때문에 메모리 단편화 이슈에서 자유로울 수 없을 거 같은데 고수분들은 어떻게 생각하시는지 궁금합니다. ==> 아이템마다 malloc/free를 하는 것이 아니라 큰 메모리 블록을 잡아놓고 그것을 잘게 쪼개서 사용할 수도 있습니다. 가령 1000개 노드가 필요하면 1000개 분량의 메모리를 malloc해서 그것을 잘게 쪼개서 사용하는 것이죠.

sheld2의 이미지

동적으로 할당하는 리스트를 써야하는 결정적인 이유는 아마도 list 내의 element 의 갯수가 얼마나 될지 정확히 알수없기 때문이 아닐까합니다. 정확히 알수는 없는반면 어느 정도의 갯수로 한정 짓겠다고하면 정적으로 메모리를 할당하여 배열리스트를 쓸수도 있지않을까요. 그리고 동적할당을 쓰면 malloc 함수호출비용(시간)이 따로 소비되겠고요. memory 할당이 실패하는 경우도 고려해야할 것 같고요. 참고로 RTOS application 에서는 리스트를 포함해서 memory 를 동적으로 할당하는 것을 전반적으로 지양합니다. 뭐 항상 그런것은 아니지만 배열구조의 리스트를 설계해서 쓰는 것이 보편적이고요.

댓글 달기

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