# RObservations #23: Solving Linked List Problems in R with R6 objects

**r – bensstats**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

# Introduction

With the `R6`

library enabling users to create object classes, it is possible to solve a variety of computer science problems using R. Following the same fashion of my previous blogs on tree search algorithms (see here, here, here and here), in this blog I explore solving linked list problems using R.

The codes written here are based on Alvin the Programmer’s tutorial on linked list problems for technical interviews on the FreeCodecamp Youtube channel. So if you want to follow my learning experience, check out the video below. Thank you Alvin for making the educational content!

# What is a linked list?

Using GeeksforGeeks’ definition, a linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers. In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

This can actually be visualized with the `ggplot2`

and `ggdag`

packages.

library(tidyverse) library(ggdag) dagify(d~c, c~b, b~a) %>% tidy_dagitty() %>% mutate(x=c(1,2,3,4), y=c(1,1,1,1), xend=c(1.99,2.99,3.99,NA), yend=c(1,1,1,NA)) %>% ggdag()+ theme_dag()+ ylim(0.95,1.10)+ annotate("text", x=1, y=1.02,label="Head")+ annotate("text", x=4, y=1.02,label="Tail")+ annotate("text", x=1.5, y=0.995,label="next")+ annotate("text", x=2.5, y=0.995,label="next")+ annotate("text", x=3.5, y=0.995,label="next")+ annotate("text", x=1, y=0.98,label="node")+ annotate("text", x=2, y=0.98,label="node")+ annotate("text", x=3, y=0.98,label="node")+ annotate("text", x=4, y=0.98,label="node")+ ggtitle("A Linked List")+ theme(plot.title=element_text(hjust=0.5, vjust=-45))

While the above data structure appears to be simple enough. There are a variety of problems which can be presented with it. Using the `R6`

library the above linked list can be constructed with the following code.

library(R6) # Node constructor node <- R6Class("Node", list( val=NULL, nxt = NULL, initialize = function(val=NULL, nxt=NULL){ self$val <- val self$nxt <-nxt } ) ) # Make our nodes a <- node$new(val="a") b <- node$new(val="b") c <- node$new(val="c") d <- node$new(val="d") # Link them together a$nxt<- b b$nxt<- c c$nxt<- d # a -> b -> c -> d -> NULL

With the linked list created, lets explore answering problems involving linked lists. For completeness, iterative and recursive solutions are be provided.

# 1. Linked List Traversal

Traversing a linked list involves writing code that will visit each node of the list once and terminate at the end of the list. The iterative solution involves setting a current node and employing a while loop. The recursive solution just requires a if statement to check if the node is null.

# Iterative code traversal <- function(node){ current <- node while(!is.null(current[['val']])){ print(current[['val']]) current<- current[['nxt']] } } traversal(a) ## [1] "a" ## [1] "b" ## [1] "c" ## [1] "d" traversal_recursive<- function(node){ if(is.null(node[["val"]])){ return() } print(node[['val']]) traversal_recursive(node[["nxt"]]) } traversal_recursive(a) ## [1] "a" ## [1] "b" ## [1] "c" ## [1] "d" ## NULL

My one annoyance with the recursive solution is that `NULL`

is explicitly returned in the console output, but besides for that, I find it a much cleaner solution than its iterative counterpart.

# 2. Linked List Values

Getting a linked list’s values is a direct application of the traversal. Recall, that the linked list is an object whose values are not readily accessible, as such a solution for getting those values is required.

# Linked List values listValues <- function(node){ current <- node values <- c() while(!is.null(current[['val']])){ values<- c(values,current[['val']]) current<- current[['nxt']] } return(values) } listValues(a) ## [1] "a" "b" "c" "d" listValues_recursive <- function(node){ if(is.null(node[["val"]])){ return() } values<-node[['val']] values<-append(values,listValues_recursive(node[["nxt"]])) return(values) } listValues_recursive(a) ## [1] "a" "b" "c" "d"

Both solutions give the same output. If you understand recursion then the recursive code gives a cleaner solution.

# 3. Sum of Linked List Values

In this problem, numeric values are assigned to the list’s nodes. The challenge is to get the sum of all the node values. Since we know how to do a list traversal, getting the sum of the list’s nodes is also a direct application of it. The code below first creates a linked list with values assigned to each node and the iterative and recursive solutions are offered.

# Make our nodes with numbers a <- node$new(val=8) b <- node$new(val=7) c <- node$new(val=2) d <- node$new(val=1) # Link them together a$nxt<- b b$nxt<- c c$nxt<- d # Iterative Solution sumList <- function(node){ current <- node total <- 0 while(!is.null(current[['val']])){ total<- total + current[['val']] current<- current[['nxt']] } return(total) } sumList(a) ## [1] 18 # Recursive solution sumList_recursive<- function(node){ if(is.null(node[["val"]])){ return(0) } return(node[['val']] + sumList_recursive(node[['nxt']])) } sumList_recursive(a) ## [1] 18

# 4. Check if Value is in Linked List

Applying the same concept of traversal, this algorithm checks if a given value is assigned to a node in a linked list by iteratively (or recursively) looking at each value in the linked list. If there is a match, the algorithm terminates and returns `TRUE`

, otherwise the algorithm searches to the end of the list and returns `FALSE`

. The iterative and recursive solutions are shown below:

# Remake linked List a <- node$new(val="a") b <- node$new(val="b") c <- node$new(val="c") d <- node$new(val="d") # Link them together a$nxt<- b b$nxt<- c c$nxt<- d # Iterative Solution inList <- function(node,target){ current<-node while(!is.null(current[['val']])){ if(current[["val"]] == target){ return(TRUE) }else{ current <-current[['nxt']] } } return(FALSE) } # Test cases inList(a,'c') ## [1] TRUE inList(a,'g') ## [1] FALSE # Recursive solution inList_recursive <- function(node,target){ if(is.null(node[["val"]])){ return(FALSE) } if(node[['val']]==target){ return(TRUE) } inList_recursive(node[['nxt']],target) } # Test cases inList_recursive(a,'c') ## [1] TRUE inList_recursive(a,'g') ## [1] FALSE

# 5. Get Node Value

This problem involves creating a function which will allow us to access each node in a linked list based on its index. If we were using a more traditional programming language we would start our index from 0. However with R we start from 1. The iterative and recursive solutions are listed below.

# Iterative Solution nodeValue<-function(node, index){ # Count value i <- 1 current<-node while(!is.null(current[["val"]])){ if(i==index){ return(current[["val"]]) } # Increment current<-current[["nxt"]] i <- i+1 } return(NULL) } # Test Cases nodeValue(a,2) ## [1] "b" nodeValue(a,1) ## [1] "a" nodeValue(a,3) ## [1] "c" nodeValue(a,4) ## [1] "d" nodeValue(a,6) ## NULL # Recursive Solution nodeValue_recursive<- function(node,index){ if(is.null(node[["val"]])){ return(NULL) } if(index==1){ return(node[["val"]]) } nodeValue_recursive(node[['nxt']],index-1) } # Test Cases nodeValue_recursive(a,2) ## [1] "b" nodeValue_recursive(a,1) ## [1] "a" nodeValue_recursive(a,3) ## [1] "c" nodeValue_recursive(a,4) ## [1] "d" nodeValue_recursive(d,6) ## NULL

# 6. Linked List Reversal

One of the more popular problems presented in a coding interview (so I was told) is the problem of “reversing” a linked list. This involves writing code which will reverse the order of the list’s nodes. To solve this, we need to declare a variable which will store a nodes “next” value as its previous value and work iteratively (or recursively) across the list. Since the algorithm starts from the beginning of the list, the first previous value is defined as `NULL`

.

The iterative solution is:

reverseList<- function(node){ prev<- NULL current<- node while(!is.null(current)){ nxt<-current[['nxt']] current[['nxt']]<-prev prev <-current current<-nxt } return(prev) } # Reverse the list and check if the list was reversed reverseList(a) %>% listValues() ## [1] "d" "c" "b" "a"

Its important to note that the list reversal affects each of the node properties and the list as a whole. If we look at node `a`

we see that its next value is NULL.

# a's nxt value is null a ## <Node> ## Public: ## clone: function (deep = FALSE) ## initialize: function (val = NULL, nxt = NULL) ## nxt: NULL ## val: a

As such, for the recursive reversal we will restore the linked list to its original form by reversing from the `d`

node.

reverseList_recursive<- function(node,prev=NULL){ if(is.null(node)){ return(prev) } nxt<-node[['nxt']] node[['nxt']]<-prev reverseList_recursive(nxt,node) } # Reverse the list from the `d` node and check if the list was reversed reverseList_recursive(d) %>% listValues() ## [1] "a" "b" "c" "d"

# 7. Zipper Lists

The zipper lists problem involves two lists where the goal is to “zip” the two lists together by creating a single list with alternating nodes from each list. If the lists differ in size, then when there are no other nodes left in the shorter list, the rest of the nodes in the longer list is appended to the end of the zipped list. This is shown visually with with the visual below:

library(ggpubr) ggarrange( dagify(d~c, c~b, b~a, q~r) %>% tidy_dagitty() %>% mutate(x=c(1,2,3,1,4,2), y=c(1.5,1.5,1.5,1.1,1.5,1.1), xend=c(1.99,2.99,3.99,1.99,NA,NA), yend=c(1.5,1.5,1.5,1.1,NA,NA)) %>% ggdag()+ theme_dag()+ ylim(0.95,2)+ ggtitle("Linked Lists- Pre-Zipping")+ theme(plot.title=element_text(hjust=0.5, vjust=-10)), dagify(d~c, c~r, r~b, b~q, q~a) %>% tidy_dagitty() %>% mutate(x=c(1,3,5,2,4,6), y=c(1,1,1,1,1,1), xend=c(1.99,3.99,5.99,2.99,4.99,NA), yend=c(1,1,1,1,1,NA)) %>% ggdag()+ theme_dag()+ ggtitle("Zipped List")+ theme(plot.title=element_text(hjust=0.5, vjust=-10)), nrow = 2 )

The iterative code for this solution is:

# First lets make our two separate lists ########## # List 1 # ########## a <- node$new(val="a") b <- node$new(val="b") c <- node$new(val="c") d <- node$new(val="d") # Link them together a$nxt<- b b$nxt<- c c$nxt<- d ########## # List 2 # ########## q <-node$new(val="q") r<- node$new(val="r") q$nxt<-r zipList<- function(node1,node2){ end <- node1 current1 <- node1[['nxt']] current2 <- node2 # Count i <- 0 while(!is.null(current1) & !is.null(current2)){ if(i%%2==0){ end[["nxt"]]<-current2 current2<- current2[["nxt"]] }else{ end[["nxt"]]<-current1 current1<- current1[["nxt"]] } end<- end[["nxt"]] #increment count i<- i+1 } if(!is.null(current1)){ end[["nxt"]]<-current1 } if(!is.null(current2)){ end[["nxt"]]<-current2 } return(node1) } # list the values to ensure the operation has been preformed properly zipList(a,q) %>% listValues() ## [1] "a" "q" "b" "r" "c" "d"

Since the linked lists have now been altered with the above operation. To show the iterative solution the linked lists will have to be reconstructed. The recursive solution is:

zipList_recursive<- function(node1,node2){ if(is.null(node1) & is.null(node2)){ return() } if(is.null(node1)){ return(node2) } if(is.null(node2)){ return(node1) } next1 <- node1[['nxt']] next2 <- node2[['nxt']] node1[['nxt']]<-node2 node2[['nxt']]<-zipList_recursive(next1,next2) return(node1) } # Remake Linked Lists ########## # List 1 # ########## a <- node$new(val="a") b <- node$new(val="b") c <- node$new(val="c") d <- node$new(val="d") # Link them together a$nxt<- b b$nxt<- c c$nxt<- d ########## # List 2 # ########## q <-node$new(val="q") r<- node$new(val="r") q$nxt<-r # list the values to ensure the operation has been preformed properly zipList_recursive(a,q) %>% listValues() ## [1] "a" "q" "b" "r" "c" "d"

# Conclusion

I’ve said it before, the `R6`

library changes the R language from being simply a statistical computing language to a proper programming language. The more I learn about R the more I see that there is so much more possible with it.

Thank you for reading my blog! I actually was working on this piece before my previous blog on creating a blockchain but I got distracted. If you enjoyed this content be sure to subscribe to my mailing list and all donations are happily accepted as well. Thanks again!

## Want to see more of my content?

Be sure to subscribe and never miss an update!

**leave a comment**for the author, please follow the link and comment on their blog:

**r – bensstats**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.