A linear linked list is also known as one-way list or singly linked list. A singly linked list is a sequence of nodes, where each node stores an element and a link to the next node, as shown in Figure 3.12 The elements in a singly linked list may or may not be stored in consecutive memory locations, so pointers are used to maintain a linear order.

Figure 3.12: Singly link list building block and example

Each node in a linked list consists of an element field and a next field. The Element field of a linked list stores the item value and Next points to the next node. In the last node, Next points to NULL value. Before getting into implementation of singly linked lists, we should focus on defining the ADT requirements for linked lists.

Figure 3.13: An example of ADT for linked list

The ADT may depend on the problem requirement. The first item in ADT is to set up an environment:

create_emptyenv <- function() {
  emptyenv()
}

The linked list can also be represented as an ordered tuple  where e_n is the n^th term in the linked list. The empty link is represented by the tuple notation <>. The create_emptyenv() function creates an empty environment, which can hold a collection of named objects and a pointer to an enclosing environment. Before creating a new list, the isEmpty() function checks if the list is empty or not, using an identical function from R.

isEmpty <- function(llist) {
  if(class(llist)!= "linkList") warning("Not linkList class")
identical(llist, create_emptyenv())
}

The next step is to define a linked list node as shown in Figure 3.6(a):

linkListNode <- function(val, node=NULL) {
  llist <- new.env(parent=create_emptyenv())
llist$element <- val
llist$nextnode <- node
class(llist) <- "linkList"
llist
}

In the linkListNode() function, an element contains element and nextnode. The element field stores the item value, and nextnode points to the next linked list node. An example of a linked list can be created using the linkListNode function as follows:

LList <-linkListNode(5,linkListNode(2,create_emptyenv()))

The constructed list can be dynamically expanded by adding and deleting nodes. The elements and nodes in a linked list can be accessed using functions, as follows:

setNextNode<-function(llist){
  llist$nextnode
}
setNextElement<-function(llist){
  llist$element
}

The next part of ADT is to get the size of the linked list. The size of a linked list requires a pointer to scan through the linked list. The scanning is implemented using recursion in R.

sizeLinkList<-function(llist, size=0){
  if (isEmpty(llist)) 
{
return(size)
} else
{
size<-size+1L
sizeLinkList(llist$nextnode, size)
}
}

The sizeLinkList function starts from the first position, and keeps scanning the list nodes till it finds an empty environment. Similarly, the addition of an item can be performed at the start, end, or at any position in the linked list. To add a linked list node at the start, just connect the pointer to the existing linked list as shown in Figure 3.14 Similarly, add a linked list node at the end by updating the empty pointer to the newly created node. To add an element in between, the node needs to be updated as shown in Figure 3.15.

Figure 3.14: Addition of an element to an existing link list

The implementation of insertion at start is done as follows:

addElement<-function(new, llist) 
{
  if (isEmpty(llist)) {
llist<-linkedlist(new)
} else
{
llist<-linkListNode(llist, new)
}
llist
}

Figure 3.15: Addition of an element in between items in the list

The deletion implementation follows a similar principle as addition (shown in Figure 3.15) by skipping the node to be deleted, and updating links accordingly:

delElement<-function(llist, pos=NULL){
  if(is.null(pos)) warning("Nothing to delete")
listsize<-sizeLinkList(llist)
if(pos>listsize) stop("Position greater than size of list")
if (isEmpty(llist)) {
warning("Empty List")
} else if(pos==1){
PreviousNode<-llist$nextnode
} else 
{
PreviousNode<-linkListNode(llist$element)
for(i in 1:(listsize-1)){
if(pos==(i+1)){
    PreviousNode$nextnode<-setNextNode(llist$nextnode)
  } else
  {
    PreviousNode$nextnode<-llist$nextnode
    llist<-llist$nextnode
  }
}
}
return(PreviousNode)
}

Searching for an item can be implemented by recursively scanning through the linked list from the starting position till the end:

findItem<-function(llist, item, pos=0, itemFound=FALSE){
  if (itemFound==TRUE) 
{
return(itemFound)
} else if(isEmpty(llist)){
return(FALSE)
} else
{
pos<-pos+1L
if(llist$element==item) itemFound<-TRUE
findItem(llist$nextnode, item, size, itemFound)
}
}

The function will return TRUE if it finds an item, otherwise it will return FALSE.

A doubly linked list extends a linear linked list by including pointers to the previous and the next node, as shown in Figure 3.16:

Figure 3.16: Doubly-linked list node

The pointers on both sides allow moving in both directions. For a one-node linked list, the previous and next pointers are set to NULL. The two pointers make this data structure more memory intensive as compared to a single linked list. Similar to singly linked list, a doubly linked list's start and end locations are referred to as the head and tail respectively. The dlinkListNode function provides the definition to create a doubly linked list node.

dlinkListNode <- function(val, prevnode=NULL, node=NULL) {
  llist <- new.env(parent=create_emptyenv())
llist$prevnode <- prevnode
llist$element <- val
llist$nextnode <- node
class(llist) <- "dlinkList"
llist
}

An example of a doubly linked list created using the preceding node structure will look like what is shown in Figure 3.17:

Figure 3.17: An example of doubly link list

A circular linked list extends both singly and doubly linked lists by connecting the null connection with the tail and head accordingly. The circular linked list extension from a singly linked list and doubly linked list is shown in Figure 3.18:

Figure 3.18: An example of circular linked lists

This can be obtained by passing the list to the null node of the linked list. For example, a singly linked list can be converted into a circular linked list by passing the head of the linked list to the tail node:

cicularLinkList<-function(llist, val){
  if(isEmpty(llist)){
llist<-linkListNode(val)
head<-llist
} else
{
llistNew<-linkListNode(val)
llistNew$nextnode<-head
llist<-linkListNode(llist, llistNew) 
}
llist
}

The circular linked list has usage in multiplayer games such as the bridge card game, where the pointer keeps moving from one player to another player in a circular fashion till the game ends.