Sun Apr 25 2021
Linked list
A linked list is made up of a series of objects, called the nodes of the list. Because a list node is a distinct object. Linked lists are among the simplest and most common data structures.
The principal benefit of a linked list over a conventional array is that the list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk, while an array has to be declared in the source code, before compiling and running the program. Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.
Singly Linked list
Singly linked lists contain nodes which have a data field as well as a next field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.
Doubly Linked list
Different from a singly linked list, a doubly linked list allows us to go in both directions - forward and reverse. Such lists allow for a great variety of quick update operations, including insertion and removal at both ends, and in the middle. A node in a doubly linked list stores two references - a next link, which points to the next node in the list, and a prev link, which points to the previous node in the list.
File Name: singly-linkedlist-algorithm.c
/* Singly Linked list */
/* Insert node at beginning */
addFirst(String newData):
create a new node v containing newData
v.setNext(head)
head = v
size = size + 1
/* Insert node at end */
addLast(String newData):
create a new node v containing newData
v.setNext(null)
/* list is empty */
if (head == null) {
head = v
/* list is not empty */
} else {
tail.setNext(v)
}
tail = v
size = size + 1
/* Delete node */
remove()
if (head = = null) then
Indicate an error: the list is empty
tmp = head
head = head.getNext()
tmp.setNext(null)
size = size - 1
/* Traverse linked list */
traverseList()
curNode = head
while (curNode != null) {
/* print out the contents of the current node */
curNode = curNode.getNext()
}File Name: doubly-linkedlist-algorithm.c
/* Doubly Linked list */
/* Insert node at beginning */
addFirst(v):
/* the current first node */
w = header.getNext()
v.setNext(w)
w.setPrev(v)
header.setNext(v)
v.setPrev(header)
size++
/* Insert node at end */
addAfter(v, z):
w = v.getNext()
v.setNext(z)
z.setPrev(v)
z.setNext(w)
w.setPrev(z)
size++
/* Delete node */
remove():
/* the current last node */
v = trailer.getPrev()
if (v = = header) then
Indicate an error: the list is empty
prev = v.getPrev()
prev.setNext(trailer)
trailer.setPrev(prev)
v.setPrev(null)
v.setNext(null)
size--