Head Pointer Keeps Being Read as Null Linked List C++

Singly Linked List

In the previous lecture, nosotros have seen some applications of the arrays. Arrays are overnice and simple for storing things in a sure order, but they have drawbacks.

In this lecture, we explore an of import alternate implementation of the data structure that stores a sequence of elements -- linked list.

Definition: A linked list is a collection of nodes that together form a linear ordering. It takes many different forms and implementation. In its most simplest form, a singly linked list is a linked listing where each node is an object that stores a reference to an element and a reference, chosen next, to another node. Annotation that a node is defined in terms of itself, which is chosen self-referential structure.

Terminologies:

• The side by side reference inside a node tin can be viewed every bit a link or arrow to some other node.
• The first and last node of a linked listing usually are chosen the head and tail of the listing, respectively. Thus, nosotros tin can traverse the list starting at the head and ending at the tail. The tail node is a special node, where the next arrow is always pointing or linking to a nil reference, indicating the end of the list.

Implementations: At that place are usually two forms of linked list:

• Without a dummy head (refer to the top singly linked listing in the following diagram), or
• With a dummy head (bottom 1). Dummy headers are oftentimes used because they help with the implementation.

Unlike an array, a singly linked list does not take a predetermined stock-still size, and uses space proportional to the number of its elements. Yet, since we do not proceed runway of whatever index numbers for the nodes in a linked list, nosotros cannot tell just by examining a node if it is the second, or fifth node in the list.

Based on the above description of a singly linked list, what is the ADT for singly linked lists?

Here is an implementation of the node of a singly linked listing with elements equally graphic symbol strings.

/** Node of a singly linked list of strings. */
public class Node {
  individual String element; // we assume elements are character strings
  individual Node side by side;
  /** Creates a node with the given element and next node. */
  public Node(Cord s, Node n) {
chemical element = southward;
adjacent = n;
}
  /** Returns the element of this node. */
  public String getElement() { return element; }
  /** Returns the next node of this node. */
  public Node getNext() { return next; }
  // Modifier methods:
  /** Sets the chemical element of this node. */
  public void setElement(String newElem) { element = newElem; }
  /** Sets the side by side node of this node. */
  public void setNext(Node newNext) { next = newNext; }
}

And the following is an incomplete implementation of the singly linked list:

/** Singly linked list .*/
public grade SLinkedList {
  protected Node caput; // head node of the list
  protected long size; // number of nodes in the listing
  /** Default constructor that creates an empty listing */
  public SLinkedList() {
head = null;
size = 0;
}
  // ... update and search methods would go here ...
}

What near the instance with a dummy caput?

/** Singly linked listing .*/
public course SLinkedList {
  protected Node head; // head node of the list
  protected long size; // number of nodes in the list
  /** Default constructor that creates an empty list */
  public SLinkedList() {
head = new Node(null, null); // create a dummy caput
size = 0;
}
  // ... update and search methods would get hither ...
} Insertion in a Singly Linked List

Insertion at the head

Insert a new node at the head of the list is straightforward. The main idea is that we create a new node, fix its next link to refer to the current head, and and then ready head to point to the new node.

Algorithm addFirst(Cord newData):
create a new node v containing newData
  v.setNext(head)
head = v
size = size + ane

Java code:

public void addFirst(Cord newData)
{
head = new Node(newData, head);
size++;
}


The higher up is the case with no dummy caput. What nearly the instance with a dummy head?

Insertion at the tail

If nosotros keep a reference to the tail node, then it would be easy to insert an element at the tail of the list. Assume we keep a tail node in the class of SLinkedList, the idea is to create a new node, assign its side by side reference to bespeak to a cipher object, set the next reference of the tail to point to this new object, and and then assign the tail reference itself to this new node. Initially both head and tail point to nix object.

Algorithm addLast(Cord newData):
  create a new node v containing newData
v.setNext(null)
if (head == null) { // list is empty
head = 5
} else { // listing is non empty
tail.setNext(5)
}
tail = v
size = size + one

What if nosotros do not know go along a reference to the tail node? How can we modify the code to implement addLast?

For a singly linked list with a dummy head, is the code the same?

Deletion in a Singly Linked List

Deletion at the head

Removal of an element at the caput of a singly linked list is relatively easy. However removing a tail node is not easy.

Algorithm removeFirst()
if (head = = nada) and then
Indicate an mistake: the list is empty
tmp = head
head = caput.getNext()
tmp.setNext(goose egg)
size = size - i

What nearly a singly linked list with a dummy head?

Traversing a Singly Linked List

Stepping through, or traversing, all the entries of a linked list from beginning to end post-obit the chain of references is a useful performance in exercise. Moreover, this procedure may be enhanced to search for and locate specific nodes.

Algorithm traverseList()
curNode = head
while (curNode != null)  {
// print out the contents of the current node
curNode = curNode.getNext()
}

What virtually a singly linked listing with a dummy head?

How to make a copy of a linked list?

Another Implementation of a Singly Linked List

Let'due south look at another possible implementation of the singly linked list. Note that this implementation is a singly linked list with a dummy head. Nosotros use nested course for the implementation.

public form SimpleList {
private Node head = new Node(cipher, cypher); // dummy head
individual int size;

public void addFirst(Object object) {
head.adjacent = new Node(object, head.next);
size++;
}

public void addLast(Object object) { // here I don't need a tail reference
Node temp = head;
while(temp.adjacent != nix)
temp = temp.next;

temp.next = new Node(object, null);
size++;
}

public Object starting time() {
if (size == 0) throw new IllegalStateException("the list is empty");
return head.next.object;
}

public boolean isEmpty() {
render (size == 0);
}

public Object removeFirst() {
if (size == 0) throw new IllegalStateException("the list is empty");

Object object = head.next.object;
head.next = head.next.next;
size--;
return object;
}

public int size() {
return size;
}

private static class Node { // the Node class is defined within the SimpleList class
Object object;
Node next;

Node(Object object, Node next) {
this.object = object;
this.adjacent = next;
}
}
}

Important: Inserting a node into or deleting a node from a linked listing follows a strict sequence of steps. Irresolute the social club of the steps in the sequence would lead to incorrect results.

Programming Exercises Given the singly-linked listing data construction stated above, implement the post-obit methods:

1. removeLast(): removes the last element in the list.
2. addAfter(Node current, Object newData): adds a node after the current node.
3. getNth(int index): takes an integer alphabetize and returns the data object stored in the node at the alphabetize position.
4. deleteNth(int index): takes an integer index and deletes the node at the index position.

Comparison Between Array and Linked List

Operations	Array	Linked List
Access	Random, 1 step	Sequential, n steps
Insertion/Deletion	Move entries over	Other entries remain the same
Storage	Allocated when it is declared, drawback of under/over-estimating space requirement	Allocated only when needed, but links consume actress infinite

viveirospunfied.blogspot.com

Source: https://www.cpp.edu/~ftang/courses/CS240/lectures/slist.htm

Share this post