What is a circular linked list?

Question

can you please share your ideas about circular linked list? and do you know how to sort names using it?

Answer 1

Best Answer - Chosen by Asker

A linked list is a data structure in which each element contains the data you want to store, and a reference to the next element.

A circular linked list is a linked list where the 'last' element includes a reference to the 'first' element. I'm putting quotes around first and last, because the linked list is now circular, so there's no first and last anymore. It's kind of like a necklace that consists of all identical shackles; such a necklace doesn't have a beginning nor end, either.

It should be clear by now that you can't sort a circular linked list: the 'first' element might be bigger than the 'last' one, but since they are connected to each other (the list is circular!), they are no longer in order.

To illustrate: here's a regular linked list that contains the letters a, b, c and d:

b --- d --- c --- a

The letters are the data, the dashes are the links. A circular list would have dash between the last element (a) and the first (b):

b --- d --- c --- a
|___________|

A sorted linked list would of course be like this:

a --- b --- c --- d

A circular sorted linked list can't exist

a --- b --- c --- d
|____      ____|

because, in this case, the letters are sorted alphabetically, but obviously the 'd' does NOT come before the letter 'a' even though the line between them does suggest that. To illustrate this, I 'broke' the line from d to a.

Asker's Rating:

Asker's Comment:

well the explanation is just ok

Answer 2

Hm.. Just click sort

Answer 3

ok I'm going to pseudo talk this through, since you didn't mention a language, and i'm rusty on my c++.

A linked list is a list of something you have like in an array or vector, and you add and remove things by pointing (with pointers like -> or something) to a certain position, and doing your add or remove. Lets just stick with adding something right now. Remove has the same concept.

So you point to somewhere in your vector (like an array, but you dont have to specify length in the beginning) and you want to add a name. You point with the pointers, allocate another space, and add the name in that spot. Alternatively, not using linked list to put something in the middle of an array or vector will require you to find the spot, and move all the other allocated spaces over one, which will probably require a for loop, and take up more memory.

in sorting names, you would first add a name, then check the input of the second name, and if it goes after the first name, put it int he second spot. Check (input) of the third name, if it goes at the end, put your pointer at the end of the vector and add it there, if it goes in between the first and second name, point to the middle (aka right after the name of the previous letter), and add it there.

Hope you get it, I cant really explain it too well, and it is 4am.

Answer 4

it is a link that contains a list that are circular around.

Answer 5

circular linked list is normal linked list except that the last node linked to the first one so it can be shown as circular shape . .

the most advantage of it that if you want to go from the last node to the first node it cost just one move .
In normal linked list moving from last node to the first one cost N-move

where is N = number of nodes in the list

you can sort it by traverse over nodes and comparing names , like any other lists

Answer 6

A link list is a programming construct. You have a series of cells and each cell has a data section and a pointer section. each cell points to the next cell in the list and the last cell points to the first to make it circular.

Look here for a visual: http://lcm.csa.iisc.ernet.in/dsa/node25.…


You can program a sort like this to bubble up the answer. THis is suedo code.

temp=0
p=getfirstpointoflist(list)

repeat

if list(d).p > list(d).next then
temp=list(d).next
list(d).next=list(d).p
list(d).p=temp
end if

p=list.next

until done