Singly-linked list. Internal representation.
Every node of a singly-linked list contains following information:
- a value (user's data);
- a link to the next element (auxiliary data).
Sketchy, it can be shown like this:
First node called head and no other node points to it. Link to the head is usually stored it the class, which provides an interface to the resulting data structure. For empty list, head is set to NULL.
Also, it makes sense to store a link to the last node, called tail. Though no node in the list can be accessed from the tail (because we can move forward only), it can accelerate an add operation, when adding to the end of the list. When list is big, it reduces add operation complexity essentially, while memory overhead is insignificant. Below you can see another picture, which shows the whole singly-linked list internal representation:
Code snippets
Commonly, the whole structure of singly-linked list is put into two classes. Main class, SinglyLinkedList, is a public interface and SinglyLinkedListNode mean for private use inside the main class. Because of SinglyLinkedListNode is auxiliary class, it's not necessary to encapsulate its fields (make them private). Notice, that SinglyLinkedList interface class may be replaced by another one, such as a Stack class, while internal implementation of the stack remains a singly-linked list.
Java implementation
public class SinglyLinkedListNode {
public int value;
public SinglyLinkedListNode next;
public SinglyLinkedListNode(int value) {
this.value = value;
next = null;
}
}
public class SinglyLinkedList {
private SinglyLinkedListNode head;
private SinglyLinkedListNode tail;
public SinglyLinkedList() {
head = null;
tail = null;
}
}
C++ implementation
class SinglyLinkedListNode {
public:
int value;
SinglyLinkedListNode *next;
SinglyLinkedListNode(int value) {
this->value = value;
next = NULL;
}
};
class SinglyLinkedList {
private:
SinglyLinkedListNode *head;
SinglyLinkedListNode *tail;
public:
SinglyLinkedList() {
head = NULL;
tail = NULL;
}
}
Recommended books
- Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
- Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
- Robert Lafore. Data Structures and Algorithms in Java. (Practice)
- Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)
| Previous: Singly-linked list overview | Next: Singly-linked list traversal |
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!