2

I'm trying to wrap my head around linked lists (which I will call SLI for now) and tries I was wondering if anyone could confirm following (or explain where I my reasoning is wrongg)

In a SLI, you start with a single node (first node, indicating the start of a SLI) which points to NULL (indicating the end of a SLI).

When adding a value to the SLI, a new node is created by creating a node, assigning the value to it and having it point NULL. After which the first node points to the new node (an not to NULL).

  • When we have a SLI with five values {1, 3, 4, 6, 7}, every node points to the next one (given that it is not a double linked list) an the node containing 7 points to NULL.
  • Searching for a certain value can only be done by traversing the list
  • when we are at the node with value 4, unless a seperate counter was implemented, there is no way to say which node we are at (opposed to an array where we can access for example array[3]). Meaning that the nodes themselves don't have any specific name or number (apart for their address in memory and which one follows)
  • a trie, being a more complex form of a linked list, does a certain string come before another?

    ie. when going through a trie, in which order will "bard" and "fox" be presented?

    • or in another way, if you would want to print the contents of the trie, which one will be printed first?
  • 1
    • Well, first, you actually start with nothing, just a NULL pointer (empty list). Optionally, you can create an special node that will hold no data, but rather just act as a "header" node, you always ignore it, but it marks the beginning of your list (I prefer to use a NULL pointer when I have an empty list). I find all your reasoning behind linked lists to be correct. I can't say anything about tries, as I have not studied them yet, this is why I am not answering but just commenting. Sep 11 '15 at 15:38
    2

    When we have a SLI with five values {1, 3, 4, 6, 7}, every node points to the next one (given that it is not a double linked list) an the node containing 7 points to NULL.

    Correct, even though if you wanted to be more technical, you would say each node's link member, points to the next node, not the node itself, because a node has two members. A value and a link to another node.

    Searching for a certain value can only be done by traversing the list.

    Also correct, but keep in mind that if the SLI is sorted, you can stop traversing the SLI when the value you read is greater/smaller than the one searching for.

    when we are at the node with value 4, unless a seperate counter was implemented, there is no way to say which node we are at (opposed to an array where we can access for example array[3]). Meaning that the nodes themselves don't have any specific name or number (apart for their address in memory and which one follows)

    Hmmm... That's a tricky one. If you consider the array [1, 3, 4, 6, 7] (array not SLI), not even then, if you are at the member with the value 4, can you know at which part of the array you are if you don't keep a separate counter. If you mean that in arrays you have random access, which means you can say array[3], then yes you are correct that a SLI doesn't have random access.

    a trie, being a more complex form of a linked list, does a certain string come before another? ie. when going through a trie, in which order will "bard" and "fox" be presented?

    or in another way, if you would want to print the contents of the trie, which one will be printed first?

    In a try, you store the words by letter. Say we have the words cat and cut (I chose those for simplicity). Here is how the trie will look

    [a,   b,   c,   d,   e,   f,   g,   h,   i,   j,   k,   l,   m,   n,   o,   p,   q,   r,   s,   t,   u,   v,   w,   x,   y,   z,    isword]
     |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |        |
     V    V    |    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V        V
    NULL NULL  |   NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL     false
               |
               |
               V
               [a,   b,   c,   d,   e,   f,   g,   h,   i,   j,   k,   l,   m,   n,   o,   p,   q,   r,   s,   t,   u,   v,   w,   x,   y,   z,    isword]
                |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |        | 
                |    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    |    V    V    V    V    V        V
                |   NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL  |   NULL NULL NULL NULL NULL     false
                |                                                                                                   |
                |                                                                                                   |
                |                                                                                                   V
                |                                                                                                   [a,   b,   c,   d,   e,   f,   g,   h,   i,   j,   k,   l,   m,   n,   o,   p,   q,   r,   s,   t,   u,   v,   w,   x,   y,   z,    isword]
                |                                                                                                    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |        |
                |                                                                                                    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    |    V    V    V    V    V    V        V 
                |                                                                                                   NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL  |   NULL NULL NULL NULL NULL NULL     false
                |                                                                                                                                                                                                   |
                |                                                                                                                                                                                                   |
                |                                                                                                                                                                                                   V
                |                                                                                                                                                                                                   [a,   b,   c,   d,   e,   f,   g,   h,   i,   j,   k,   l,   m,   n,   o,   p,   q,   r,   s,   t,   u,   v,   w,   x,   y,   z,    isword]
                |                                                                                                                                                                                                    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |        | 
                |                                                                                                                                                                                                    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V        V
                |                                                                                                                                                                                                   NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL     true
                |
                V
                [a,   b,   c,   d,   e,   f,   g,   h,   i,   j,   k,   l,   m,   n,   o,   p,   q,   r,   s,   t,   u,   v,   w,   x,   y,   z,    isword]
                 |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |        |
                 V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    |    V    V    V    V    V    V        V
                NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL  |   NULL NULL NULL NULL NULL NULL     false
                                                                                                                |
                                                                                                                |
                                                                                                                V
                                                                                                               [a,   b,   c,   d,   e,   f,   g,   h,   i,   j,   k,   l,   m,   n,   o,   p,   q,   r,   s,   t,   u,   v,   w,   x,   y,   z,    isword]
                                                                                                                |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |        | 
                                                                                                                V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V    V        V
                                                                                                               NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL     true
    

    (That took a while...)

    So if you start from the top branch and every time you see a letter that points to a deeper level, you go down, and so on, you will print all words in alphabetical order. So cat first and then cut.


    If this answers your question please accept it by clicking the gray check-mark to the left, so that it becomes green. You can also vote it up by pressing the up arrow above the check-mark. And don't forget to keep coding!

    2
    • Is there an ASCII art badge somewhere?
      – Sam Gerber
      Sep 23 '15 at 17:48
    • 1
      I don't know I did this by hand.
      – ChrisG
      Sep 24 '15 at 5:48

    You must log in to answer this question.

    Not the answer you're looking for? Browse other questions tagged .