Implementing linked list in shell scripting

Shell Programming and Scripting
1

Hello Experts,

Is it possible to implement linked list in shell scripting? is yes then how can we do it? Any working example is highly appreciated.

Thanks in advance.

2

I'd use arrays. One for the values and one for the next index.

Here is an example of a sorted linked list:

llinsert() {
   local END=${#LST[@]}
   local i

   for((i=0; NXT; i=NXT))
   do
     if [ "${LST[NXT]}" \> "$1" ]
     then
        ((i=NXT))
        LST[END]=${LST}
        LST="$1"
        ((NXT[END]=NXT))
        ((NXT=END))
        return
     fi
   done

   LST[END]="$1"
   ((NXT=END))
   NXT[END]=0
}

llfirst() {
  pos=NXT[0]
  echo "${LST[pos]}"
}

llnext() {
   (( NXT[pos] )) && {
       ((pos=NXT[pos]))
       echo "${LST[pos]}"
   }
}

LST=("")

llinsert "please"
llinsert "sort"
llinsert "this"
llinsert "small"
llinsert "list"
llinsert "of"
llinsert "words"

llfirst
while llnext
do
  :
done

# Debug - Output array contents
echo
printf "%-4s %-8s %-3s\n" Idx LST NXT
printf "%-4s %-8s %-3s\n" --- -------- ---
for((i=0;i<${#NXT[@]};i++)) {
   printf "%-4s %-8s %-3s\n" "$i" "${LST}" "${NXT}"
}

Output:

list
of
please
small
sort
this
words

Idx  LST      NXT
---  -------- ---
0             1  
1    list     5  
2    small    4  
3    this     7  
4    sort     3  
5    of       6  
6    please   2  
7    words    0
4 Likes
3

bash already supports associative arrays, so IMO the need for linked lists may not be all that critical. Chubler XL gave a really good take on it.
Associative arrays require bash v4

 declare -A arr=( [start]=foo [foo]=bar [bar]=quux [quux]=grault [grault]=end [end]=end )
 key=start
 while [ $key != "end" ]
 do 
    echo "$key  ${arr[$key]}"
    key=${arr[$key]}
 done
3 Likes
4

Hi Chubler,

Thanks for the reply, can you please also help me to understand the example mentioned here?

5

Agreed associative arrays are quite a powerful feature, but some problems can still be better served with linked lists. Particularly when maintaining a sequence of items.

Firstly I'd like to simplify the solution I provided. I was focusing on maintaining the first array element as the list head and this introduces extra complexity and means the data values were being shuffled during inserts.

This solution maintains the inserted order in the array and simply shuffles the NXT indexes for the sorted order.

llinsert() {
   local END=${#LST[@]}
   local i

   for((i=0; NXT; i=NXT))
   do
     [ "${LST[NXT]}" \> "$1" ] && break
   done

   LST[END]="$1"
   ((NXT[END]=NXT))
   ((NXT=END))

  shift
  (($#)) && llinsert $@
}

llfirst() {
  pos=NXT[0]
  echo "${LST[pos]}"
}

llnext() {
   (( NXT[pos] )) && {
       ((pos=NXT[pos]))
       echo "${LST[pos]}"
   }
}

LST=("")

llinsert please sort this small list
llinsert of words

llfirst
while llnext
do
  :
done

# Debug - Output array contents
echo
printf "%-4s %-8s %-3s\n" Idx LST NXT
printf "%-4s %-8s %-3s\n" --- -------- ---
for((i=0;i<${#NXT[@]};i++)) {
   printf "%-4s %-8s %-3s\n" "$i" "${LST}" "${NXT}"
}

Output:

list
of
please
small
sort
this
words

Idx  LST      NXT
---  -------- ---
0             5  
1    please   4  
2    sort     3  
3    this     7  
4    small    2  
5    list     6  
6    of       1  
7    words    0

I'll start with an explanation of the data structure:

The LST array contains the key values of the sorted list. Note that LST[0] is a dummy header element and is there to simplify the code.
The NXT array contains the array index of the next element or zero when at the end of the list. NXT[0] is the index of the first element (zero for an empty list).

So in the example above, we look at NXT[0] for the list header and this gives us 5 so LST[5] ( list ) is our first element.
To find the next element we look at NXT[5] which gives us 6 so we have LST[6] ( of )
NXT[6] is 1 giving LST[1] ( please )
NXT[1] is 4; we continue in this manner
until we reach NXT[7] which is zero and we come to the end of the list.

The logic of the insert is straight forward:

   Start at the head of the list (NXT[0])
   Keep steeping thru the list using the NXT value
      until you encounter a key value which is greater than that to be inserted
      or you reach the end of the list
   place the value to be inserted at the end of the list
   set the NXT value to be the last element encountered above (index of item with a greater key or zero)

lldelete is another matter. We have two options here:

  1. Simply adjust the NXT pointers to jump over the deleted value and leave it in the LST where it was.

  2. Keep a separate free-list and re-use any deleted array values during the next insert.

  3. Will waste space in the array, but keeps the llinsert code unchanged.

If using method 2 I'd be tempted to use the NXT pointers to also keep track of the free-list. Then all you would need is a free-list-head variable with the index of the first deleted item, it's NXT value would be the next deleted item or zero when it's the last.

If you have any payload data associated with the key, simply store it in another array(s) with the same index as the key.

Hopefully, this gives you an understanding on how shell scripts can be used to implement linked lists.

2 Likes