# Implementing linked list in shell scripting

**URL:** <https://community.unix.com/t/implementing-linked-list-in-shell-scripting/365851>\
**Category:** Shell Programming and Scripting\
**Created:** [March 29, 2017, 1:36pm UTC](https://community.unix.com/t/implementing-linked-list-in-shell-scripting/365851 "2017-03-29T13:36:29Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![mukulverma2408](https://community.unix.com/letter_avatar/mukulverma2408/32/6_22734026db12803ebb3e059622ac3534.png) [@mukulverma2408](https://community.unix.com/u/mukulverma2408)\
**Post date:** [March 29, 2017, 1:36pm UTC](https://community.unix.com/t/implementing-linked-list-in-shell-scripting/365851/1 "2017-03-29T13:36:29Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Chubler\_XL](https://community.unix.com/user_avatar/community.unix.com/chubler_xl/32/2077_2.png) [@Chubler\_XL](https://community.unix.com/u/Chubler_XL)\
**Post date:** [March 29, 2017, 5:16pm UTC](https://community.unix.com/t/implementing-linked-list-in-shell-scripting/365851/2 "2017-03-29T17:16:45Z")

</div>

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

Here is an example of a sorted linked list:

```nohighlight
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:

```nohighlight
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

```

---

<div class="post-metadata">

**Author:** ![jim\_mcnamara](https://community.unix.com/letter_avatar/jim_mcnamara/32/6_22734026db12803ebb3e059622ac3534.png) [@jim\_mcnamara](https://community.unix.com/u/jim_mcnamara)\
**Post date:** [March 29, 2017, 9:37pm UTC](https://community.unix.com/t/implementing-linked-list-in-shell-scripting/365851/3 "2017-03-29T21:37:54Z")

</div>

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

```nohighlight
 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

```

---

<div class="post-metadata">

**Author:** ![mukulverma2408](https://community.unix.com/letter_avatar/mukulverma2408/32/6_22734026db12803ebb3e059622ac3534.png) [@mukulverma2408](https://community.unix.com/u/mukulverma2408)\
**Post date:** [March 30, 2017, 1:13pm UTC](https://community.unix.com/t/implementing-linked-list-in-shell-scripting/365851/4 "2017-03-30T13:13:22Z")

</div>

> [@chubler\_xl](#):
>
> I'd use arrays. One for the values and one for the next index.  
> Here is an example of a sorted linked list:

Hi Chubler,

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

---

<div class="post-metadata">

**Author:** ![Chubler\_XL](https://community.unix.com/user_avatar/community.unix.com/chubler_xl/32/2077_2.png) [@Chubler\_XL](https://community.unix.com/u/Chubler_XL)\
**Post date:** [April 2, 2017, 4:36pm UTC](https://community.unix.com/t/implementing-linked-list-in-shell-scripting/365851/5 "2017-04-02T16:36:14Z")

</div>

> [@jim mcnamara](#):
>
> bash already supports associative arrays, so IMO the need for linked lists may not be all that critical.

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.

> [@mukulverma2408](#):
>
> Hi Chubler,
> 
> Thanks for the reply, can you please also help me to understand the example mentioned here?

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.

```plaintext
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:

```plaintext
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:

```plaintext
   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.