4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (2023)

A linked list is a linear collection of data elements whose orderis not determined by the placement in memory. Instead, each element is storedin a node which points to the next node.In the next sections we implement this linked list data structure.In doing so, we need to be sure thatwe can maintain the relative positioning of the items. However, there isno requirement that we maintain that positioning in contiguous memory.For example, consider the collection of items shown inFigure 1. It appears that these values have been placedrandomly. If we can maintain some explicit information in each item,namely the location of the next item (see Figure 2), then therelative position of each item can be expressed by simply following thelink from one item to the next.

4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (1)
4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (2)

It is important to note that the location of the first item of the listmust be explicitly specified. Once we know where the first item is, thefirst item can tell us where the second is, and so on. The externalreference is often referred to as the head of the list. Similarly,the last item needs to know that there is no next item.

The basic building block for the linked list implementation is thenode. Each node object must hold at least two pieces of information.First, the node must contain the list item itself. We will call this thedata field of the node. In addition, each node must hold a referenceto the next node. Listing 1 shows the C++implementation. To construct a node, you need to supply the initial datavalue for the node. Evaluating the assignment statement below will yielda node object containing the value 93 (see Figure 3). Youshould note that we will typically represent a node object as shown inFigure 4. The Node class also includes the usual methodsto access and modify the data and the next reference.

Listing 1

#include <iostream>using namespace std;class Node { private: int data; //data in the beginning node Node *next; //pointer to the next node public: Node(int initdata) { data = initdata; //the initialized data is set as the head next = NULL; //the next node is set as NULL, as there is no next node yet. } int getData() { //function that return data of a given node. return data; } Node *getNext() { return next; } void setData(int newData) { data = newData; } void setNext(Node *newnext) { next = newnext; }};
>>> temp = Node(93) //sets the nodes data to the integer 93>>> temp.getData() // calls the getData() function.93

The special C++ reference value NULL will play an important rolein the Node class and later in the linked list itself. A referenceto NULL will denote the fact that there is no next node.

Note:

in the constructor that a node is initially created with next and a pointer toNULL. Since this is sometimes referred to as “grounding the node,”we will use the standard ground symbol to denote a reference that isreferring to NULL.

4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (3)
4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (4)

As we suggested above, the unordered linked listwill be built from a collection of nodes, each linked to the next by explicitpointers. As long as we know where to find the first node (containing the firstitem), each item after that can be found by successively following thenext links. With this in mind, the UnorderedList class must maintaina reference to the first node. Listing 2 shows theconstructor. Note that each list object will maintain a single referenceto the head of the list.

Listing 2

class UnorderedList { public: Node *head; UnorderedList() { head = NULL; }}

Initially when we construct a list, there are no items. The assignment and declarationstatement

UnorderedList myList;

creates the linked list representation shown inFigure 5. As we discussed in the Node class, thespecial reference NULL will again be used to state that the head ofthe list does not refer to anything. Eventually, the example list givenearlier will be represented by a linked list as shown inFigure 6. The head of the list points to the first nodewhich contains the first item of the list. In turn, that node holds areference to the next node (the next item) and so on. It is very important to note that the list class itself does not contain any nodeobjects. Instead it contains a single pointer to only the first nodein the linked structure.

    Q-1: What would happen if you lose the head of a singularly-linked linked list?

  • If you lose the head, the next node becomes the head.
  • No, if you lose the head node, your pointer will be pointing at nothing.
  • If you lose the head, the list is still in memory, you just cannot find it.
  • Yes, this occurs because the delete keyword is never used to get rid of the list.
  • It is impossible to lose the head.
  • No, if you lose the head node, your pointer will be pointing at nothing.
  • If you lose the head, you lose access to the entire linked list.
  • Right, however, it remains in memory, unknown to you.

Listing 2

Initially when we construct a list, there are no items. The assignmentstatement

>>> mylist = UnorderedList()
4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (5)
4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (6)

The isEmpty method, shown in Listing 3, simply checks tosee if the head of the list is a reference to NULL. The result ofthe boolean expression this->head==NULL will only be true if thereare no nodes in the linked list. Since a new list is empty, theconstructor and the check for empty must be consistent with one another.This shows the advantage to using the reference NULL to denote the“end” of the linked structure. Two references are equal if they both refer to the sameobject. We will use this often in our remaining methods.

Listing 3

bool isEmpty() { return head == NULL;}

So, how do we get items into our linked list? We need to implement the addmethod. However, before we can do that, we need to address the importantquestion of where in the linked list to place the new item. Since this linkedlist is unordered, the specific location of the new item with respect tothe other items already in the linked list is not important. The new item cango anywhere. With that in mind, it makes sense to place the new item inthe easiest location possible.

Recall that the linked list structure provides us with only one entrypoint, the head of the linked list. All of the other nodes can only be reachedby accessing the first node and then following next links. Thismeans that the easiest place to add the new node is right at the head,or beginning, of the linked list. In other words, we will make the new item thefirst item of the linked list and the existing items will need to be linked tothis new first item so that they follow.

The linked linked list shown in Figure 6 was built by callingthe add method a number of times.

>>> mylist.add(31)>>> mylist.add(77)>>> mylist.add(17)>>> mylist.add(93)>>> mylist.add(26)>>> mylist.add(54)

Note that since 31 is the first item added to the linked list, it willeventually be the last node on the linked list as every other item isadded ahead of it. Also, since 54 is the last item added, it will becomethe data value in the first node of the linked list.

The add method is shown in Listing 4. Each item of the linked listmust reside in a node object. Line 2 creates a new node and places theitem as its data. Now we must complete the process by linking the newnode into the existing structure. This requires two steps as shown inFigure 7. Step 1 (line 3) changes the next referenceof the new node to refer to the old first node of the linked list. Now that therest of the linked list has been properly attached to the new node, we canmodify the head of the linked list to refer to the new node. The assignmentstatement in line 4 sets the head of the linked list.

The order of the two steps described above is very important. Whathappens if the order of line 3 and line 4 is reversed? If themodification of the head of the linked list happens first, the result can beseen in Figure 8. Since the head was the only externalreference to the linked list nodes, all of the original nodes are lost and canno longer be accessed.

Listing 4

4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (7)
4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (8)

The next methods that we will implement – size, search, andremove – are all based on a technique known as linked listtraversal. Traversal refers to the process of systematically visitingeach node. To do this we use an external reference that starts at thefirst node in the linked list. As we visit each node, we move the reference tothe next node by “traversing” the next reference.

To implement the size method, we need to traverse the linked listand keep a count of the number of nodes that occurred.Listing 5 shows the C++ code for counting the number ofnodes in the linked list. The external reference is called current and isinitialized to the head of the linked list in line 2. At the start of theprocess we have not seen any nodes so the count is set to \(0\).Lines 4–6 actually implement the traversal. As long as the currentreference has not seen the end of the linked list (NULL), we move currentalong to the next node via the assignment statement in line 6. Again,the ability to compare a reference to NULL is very useful. Everytime current moves to a new node, we add \(1\) to count.Finally, count gets returned after the iteration stops.Figure 9 shows this process as it proceeds down the linked list.

Listing 5

int size() { Node *current = head; int count = 0; while (current != NULL) { count++; current = current->getNext(); } return count;}
4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (9)

Searching for a value in a linked list implementation of an unorderedlinked list also uses the traversal technique. As we visit each node in thelinked list we will ask whether the data stored there matches the itemwe are looking for. In this case, however, we may not have to traverseall the way to the end of the linked list. In fact, if we do get to the end ofthe linked list, that means that the item we are looking for must not bepresent. Also, if we do find the item, there is no need to continue.

Listing 6 shows the implementation for the search method.As in the size method, the traversal is initialized to start atthe head of the linked list (line 2). As long as there aremore nodes to visit and we have not found the item we are looking for,we continue to check the next node. The question in line 4 asks whetherthe data item is present in the current node. If so, we return True.When we reach the end of the list and the item has not been found, we return False.

Listing 6

bool search(int item) { Node *current = head; while (current != NULL) { if (current->getData() == item) { return true; } else { current = current->getNext(); } } return false;}

    Q-2: True / false: The while loop is needed to keep the traversal from going past the end of the list.

  • True
  • Correct!
  • False
  • Not quite, without the while loop, the traversal could go for as long as the program is allowed to run.

As an example, consider invoking the search method looking for theitem 17.

>>> mylist.search(17)1

Since 17 is in the linked list, the traversal process needs to move only to thenode containing 17. At that point, the variable found is set toTrue and the while condition will fail, leading to the returnvalue seen above. This process can be seen in Figure 10.

4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (10)

The remove method requires two logical steps. First, we need totraverse the linked list looking for the item we want to remove. Once we findthe item (recall that we assume it is present), we must remove it. Thefirst step is very similar to search. Starting with an externalreference set to the head of the linked list, we traverse the links until wediscover the item we are looking for. Since we assume that item ispresent, we know that the iteration will stop before current gets toNULL. This means that we can simply use the boolean found in thecondition.

When found becomes True, current will be a reference to thenode containing the item to be removed. But how do we remove it? Onepossibility would be to replace the value of the item with some markerthat suggests that the item is no longer present. The problem with thisapproach is the number of nodes will no longer match the number ofitems. It would be much better to remove the item by removing the entirenode.

In order to remove the node containing the item, we need to modify thelink in the previous node so that it refers to the node that comes aftercurrent. Unfortunately, there is no way to go backward in the linkedlist. Since current refers to the node ahead of the node where wewould like to make the change, it is too late to make the necessarymodification.

The solution to this dilemma is to use two external references as wetraverse down the linked list. current will behave just as it didbefore, marking the current location of the traverse. The new reference,which we will call previous, will always travel one node behindcurrent. That way, when current stops at the node to be removed,previous will be referring to the proper place in the linked listfor the modification.

Listing 7 shows the complete remove method. Lines 2–3assign initial values to the two references. Note that currentstarts out at the linked list head as in the other traversal examples.previous, however, is assumed to always travel one node behindcurrent. For this reason, previous starts out with a value ofNULL since there is no node before the head (seeFigure 11). The boolean variable found will again beused to control the iteration.

In lines 6–7 we ask whether the item stored in the current node is theitem we wish to remove. If so, found can be set to True. If wedo not find the item, previous and current must both be movedone node ahead. Again, the order of these two statements is crucial.previous must first be moved one node ahead to the location ofcurrent. At that point, current can be moved. This process isoften referred to as “inch-worming” as previous must catch up tocurrent before current moves ahead. Figure 12 showsthe movement of previous and current as they progress down the linkedlist looking for the node containing the value 17.

Listing 7

void remove(int item) { Node *current = head; Node *previous = NULL; bool found = false; while (!found) { if (current->getData() == item) { found = true; } else { previous = current; current = current->getNext(); } } if (previous == NULL) { head = current->getNext(); } else { previous->setNext(current->getNext()); }}
4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (11)
4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (12)

Once the searching step of the remove has been completed, we need toremove the node from the linked list. Figure 13 shows thelink that must be modified. However, there is a special case that needsto be addressed. If the item to be removed happens to be the first itemin the linked list, then current will reference the first node in thelinked list. This also means that previous will be NULL. We saidearlier that previous would be referring to the node whose nextreference needs to be modified in order to complete the remove. In thiscase, it is not previous but rather the head of the linked list that needsto be changed (see Figure 14).

4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (13)
4.3. Implementing an Unordered Linked List — Problem Solving with Algorithms and Data Structures using C++ (14)

Line 12 allows us to check whether we are dealing with the special casedescribed above. If previous did not move, it will still have thevalue NULL when the boolean found becomes True. In that case(line 13) the head of the linked list is modified to refer to the node afterthe current node, in effect removing the first node from the linkedlist. However, if previous is not NULL, the node to be removed issomewhere down the linked list structure. In this case the previousreference is providing us with the node whose next reference must bechanged. Line 15 uses the setNext method from previous toaccomplish the removal. Note that in both cases the destination of thereference change is current.getNext(). One question that oftenarises is whether the two cases shown here will also handle thesituation where the item to be removed is in the last node of the linkedlist. We leave that for you to consider.

You can try out the UnorderedList class in ActiveCode 1.

The remaining methods append, insert, index, and pop areleft as exercises. Remember that each of these must take into accountwhether the change is taking place at the head of the linked list or someplaceelse. Also, insert, index, and pop require that we name thepositions of the linked list. We will assume that position names are integersstarting with 0.

Self Check

    Q-4: Select the correct statement below.

  • Every Node is contained within the UnorderedList class object. Making access to every Node of the linked list possible.
  • Wrong! An UnorderedList class object will only reference the first item of the linked list.
  • Every Node in the linked list is exactly one space in memory away from the next. Making it possible to find the next Node and traverse through the list.
  • Wrong! A Node in a linked list can be in various locations in memory. This is very important to understand how linked lists operate.
  • Every Node in the list is in various locations in memory, and those memory addresses are stored in an array inside of the UnorderedList object, which makes accessing each Node possible.
  • Wrong! While every Node can and will likely be in various locations in memory, all those locations will not be contained in the UnorderedList class object.
  • Every Node in the list is in various locations in memory, and each Node contains a pointer to the next Node in the list without needing to be contained in the UnorderedList class.
  • Correct! An unordered linked list class object will have a pointer to the first Node of the list. That Node will contain a pointer to the second Node of the list, and so on.

If you had a rough time with understanding the use of pointers in the question above, it might be a good idea to look back at chapter 1.9 and review how pointers work again.

Part I: Implement the append method for UnorderedList. What is the time complexity of the method you created?

Part II: In the previous problem, you most likely created an append method that was \(O(n)\) If you add an instance variable to the UnorderedList class you can create an append method that is \(O(1)\). Modify your append method to be \(O(1)\) Be Careful! To really do this correctly you will need to consider a couple of special cases that may require you to make a modification to the add method as well.

You have attempted of activities on this page

Top Articles
Latest Posts
Article information

Author: Tuan Roob DDS

Last Updated: 03/13/2023

Views: 6501

Rating: 4.1 / 5 (42 voted)

Reviews: 89% of readers found this page helpful

Author information

Name: Tuan Roob DDS

Birthday: 1999-11-20

Address: Suite 592 642 Pfannerstill Island, South Keila, LA 74970-3076

Phone: +9617721773649

Job: Marketing Producer

Hobby: Skydiving, Flag Football, Knitting, Running, Lego building, Hunting, Juggling

Introduction: My name is Tuan Roob DDS, I am a friendly, good, energetic, faithful, fantastic, gentle, enchanting person who loves writing and wants to share my knowledge and understanding with you.