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
Code:
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
Last edited by jim mcnamara; 03-29-2017 at 10:56 PM..
These 3 Users Gave Thanks to jim mcnamara For This Post:
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.
Quote:
Originally Posted by 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.
Code:
llinsert() {
local END=${#LST[@]}
local i
for((i=0; NXT[i]; i=NXT[i]))
do
[ "${LST[NXT[i]]}" \> "$1" ] && break
done
LST[END]="$1"
((NXT[END]=NXT[i]))
((NXT[i]=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[i]}" "${NXT[i]}"
}
Output:
Code:
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:
Code:
Start at the head of the list (NXT[0])
Keep steeping thru the list using the NXT[i] 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.
1. 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.
These 2 Users Gave Thanks to Chubler_XL For This Post:
Hi, I am programming in kernel, and I want to use a double linked list that holds infos that every process could access and modify THIS list. So, I suppose it is a 'global' variable since every process(thread) can reach it, I am wondering where to put it? by changing some of the kernel files? (1 Reply)
i have a linked list set up like
typedef struct client_list {
char *client_name;
int client_socket_fd;
struct client_list *next;
} client;
client *client_list=NULL;
before adding to the list i check if it already exists, only if it does not then i add
if (client_list==NULL... (1 Reply)
Hello Everyone,
Over the last few months I have begun to expand my programing skills from windows, Java and SQL / PL-SQL programing into the wonderful world of shell scripting. With little training budget my only options for training are books, Internet and this site (BTY... (1 Reply)
03-29-2017
