Clever Geek Handbook

Working with pointers and linked lists: how to iterate over a linked list, modify and compare keys

I am being asked to implement an algorithm based on the data structure a linkedList

in the form of pseudocode.

Unfortunately, I have a Python / Java background and therefore no experience with pointers.

Can anyone explain to me how I will iterate over the values doublyLinkedList

, modify and compare the values ​​of the elements.

From what I have understood so far, I would do something like this to have an iteration over each element.

for L.head to L.tail

But how could I access the current object in a list similar to that A[i] for i to L.length

?

How order of a linkedList is determined by pointers rather than indices in a linkedList

can I just do things like currentObj.prev.key = someVal

or currentObj.key < currentObj.prev.key

, or is there some other wokflow to work with individual elements?

Again, I am clearly stuck as I am missing a basic understanding of how to deal with pointers.

Cheers, Andrew

+3


source to share


1 answer


So basically data structures:

  • Node:

    node {
  node next;//"single link"
  node prev;//for "doubly"...
}

  • and the list:

    list {
   node head;//for singly linked, this'd be enough
   node tail;//..for "doubly" you "point" also to "tail"
   int/*long*/ size; //can be of practical use
}

(common) list operations:



  • Creation / initialization:

    list:list() {
    head = null;
    tail = null;
    size = 0;
}

  • Add a node at the first position:

    void:addFirst(node) {
   if(isEmpty()) {
     head = node;
     tail = node;
     size = 1;
   } else {
     head.prev = node;
     node.next = head;
     head = node;
     size++;
   }
}
// ..."add last" is quite analogous...

  • "empty" can be implemented in different ways ... as long as you keep the invariant

    bool:isEmpty() {
    return size==0;
    //or return head==null ... or tail==null
}

  • "add node at position i":

    void:add(i, node) {
    assert(i>=0 && i <=size);//!
    if(isEmpty() || i == 0) { 
        addFirst(node);
    } else if (i == size) {
        addLast(node);
    } else {//here we could decide, whether i is closer to head or tail, but for simplicity, we iterate "from head to tail".
      int j = 1;
      node cur = head.next; //<- a "cursor" node, we insert "before" it ;) 
      while(j < i) {//1 .. i-1 
         cur = cur.next;// move the cursor
         j++;//count
      }
      //j == i, cur.next is not null, curr.prev is not null, cur is the node at currently i/j position
      node.prev = cur.prev;
      cur.prev.next = node;
      cur.prev = node;
      node.next = cur;
   }
   //don't forget the size:
   size++;
}

  • Removing (node) is easy!

  • "Delete at position", "find node", "get node by position", etc., use a similar loop (like add(i, node)

    ) ... to find the correct index or node.

The power / advantage of a double (versus one) linked list is that it can iterate as "fourth" as "backward". To take advantage of this (this is only beneficial for index operations for "find (node)", for example, you still don't know where to start / iterate better), you determine if it is closer pos

to the head (0) or the tail (size -1), and start and iterate accordingly.

... What other operations are you interested in (in detail)?

+1


source






More articles:


All Articles