Back | Reverse | Quick Reply | Post Reply |

Linked Lists
Link | by りんーちゃん on 2008-11-15 20:54:29
I don't get it. Wikipedia (or anything on Google) doesn't help either. Dx
They say doodling helps... but still, what? |:

Additional: Doubly-linked lists. ← what?! ):
*needs an additional node WAA!!*

Help?


      
  m y . L i F E . i . t r a d e . i n . f o r . y o u r . P A i N .

Re: Linked Lists
Link | by Lanster on 2008-11-15 21:31:13
Linked list is the combination of cursor and struct
Just like array, we use linked list to keep a lot of data.
But linked list can keep a lot of data without restriction.

Linked list has 3 parameter in struct :
- Data
- *Next data
- *Previous data(for double linked list)

We use pointer next and previous, to connect two Tnodes.
We used connector next and previous to move cursor
To delete and add Tnode in linked list we need additional cursor.
That's the basic of linked list.

If you still don't know, just tell me, I can help you^^

Reinforce

Re: Linked Lists
Link | by りんーちゃん on 2008-11-15 22:19:10
Thank you Lanster. :)

hmm...
I get its point, but I don't get the logic behind all the redirection. :/
Or simply put, I have a hard time formulating algorithms for linked lists...
sample problem:


↑ Yea, something as simple as that, I cannot do. Dx

I don't get doubly-linked lists even moar~ D:
It's supposed to make accessing previous data easier, but it makes programming harder for me. >_<
I lost my logic. ):

-----
BTW, do you have Y!messenger? ^^


      
  m y . L i F E . i . t r a d e . i n . f o r . y o u r . P A i N .

Re: Linked Lists
Link | by Raizo_O on 2008-11-15 23:01:05 (edited 2008-11-15 23:28:58)
basically you have a set of data and you want to sort it by using adding node method right?

first of all you need this
http://img504.imageshack.us/my.php?image=addlinkedlistpq9.jpg

after that you can traverse the data using loop and adding them one by one using that method above

double linked list is not really that much different than single linked list

as Lanster mention before, a linked list consist of node which have head and tail.
Each node between head and tail have reference to the next node, that's basically single linked list

The difference betwee double and single is in Double linked list each node have previous reference as well

What do you think of Planetarium?
That beautiful twinkling of eternity that will never fade, no matter when.
All the stars in the sky are waiting for you.”
~Yumemi Hoshino~

Re: Linked Lists
Link | by Lanster on 2008-11-15 23:37:28
you're welcome^^

Hmmmm, I understand the logic but I can't explain it very well, since I can't speak English very well, sorry
my Y!Messenger : planster@yahoo.com
but I rarely use it XP

pHead is used as the header of the data, and it must placed in the first of the data sequence
pTail is the end of the data sequence
pRun is the cursor that help you to insert new data

But I don't know, We must input data from the other link list or from the user

So I'll explain the basic
input from the user

- We input the first data, but we don't have to sort the data because there aren't any other data
- We input the second data and check it. It's value is lower than pHead, so we must placed it in the front
- We input the third data and check it. It's value is higher than pTail, so we must placed it in the back
- We input the 4th data and check it. It's value is lower than head, so we must placed it in the front
- We input the 5th data and check it. It's value is higher than head, and lower than pTail so we need a new cursor
- We input the 6th data and check it. It's value is higher than head, and lower than pTail so we need a new cursor

Well I'll use single linked list

My logic is a little different, I do the check before inserting the data, so we can make a simpler algorithm
We don't need pRun to do it, but if you do, you can insert the data using cursor, function by reference

If it's value is lower than pHead, so we must placed it in the front, use function frontadd(data)
If it's value is higher than pTail, so we must placed it in the back, use function backadd(data)

Note : You must check the linked list before adding the data, you can find it in the link that Raizo mentioned

for 1-4
input new data
check the pTail and pHead value
compare them by using if()(<-- to use function frontadd() or backadd() ) to add the data

for 5
input new data
check the pTail and pHead value
Use function middleadd(data)

0 - 12 - 13 - 57
We must add data '1'
then make a new cusor
(for example : *help)

help = pHead
while(data< help->next){
help = help->next
}
so help cursor will point to data 0
then connect the new data container to the linked list

I'll say there is a cursor named "baru" that pointing to the new container(baru)
then do
baru->next = help->next
help->next = baru;

So the new container will be connected to the linked list


for 6
input new data
check the pTail and pHead value
Use function middleadd(data)

0 - 1 - 12 - 13 - 57
We must add data '25'
then make a new cusor
(for example : *help)

help = pHead
while(data< help->next){
help = help->next
}
so help cursor will point to data 13
then connect the new data container to the linked list

I'll say there is a cursor named "baru" that pointing to the new container(baru)
then do
baru->next = help->next
help->next = baru;

So the new container will be connected to the linked list

That's how the logic works
Oh, you can display every data that we input

Btw, do you understand the logic of adding data in the front and in the behind???
if you don't, maybe I'll explain it later..... // feel slightly sleepy
But if Raizo can translate Indonesian language to English then I can explain it easily^^
And I'm sorry if I make a mistake

Ja~

Reinforce

Re: Linked Lists
Link | by りんーちゃん on 2008-11-16 02:28:23 (edited 2008-11-16 02:57:57)
Interesting. But answering that certain problem in not my main concern because I need flexibility in problem solving. :|

How do I use malloc (memory allocation) and free() in deleting or adding nodes?
↑ I never really got that.

And the whole cursor thing still confuses me...
I'll try doodling with your explanations in a while, thanks! :)


      
  m y . L i F E . i . t r a d e . i n . f o r . y o u r . P A i N .

Re: Linked Lists
Link | by Lanster on 2008-11-16 02:43:13
I know that you want a flexible one,
but all linked list use malloc
free() is used to check the memory
free() is used when we delete data or add data
if we don't have any data, what we should do is ignore the delete command
if we don't have any data, we can add the data just by pointing pHead and pTail

We have a function to add data, delete data, search data..........
That's already flexible, but we must modify the main function that call the others function

Reinforce

Re: Linked Lists
Link | by りんーちゃん on 2008-11-16 03:02:34 (edited 2008-11-16 03:03:25)
Nice, but I don't really know how to create functions that do all those things (search, delete, add...), which is my main problem.
I can't visualize the data->node->data->node thing so I don't understand how to insert data or sort or delete (a single element).
Owhohoho~ I feel a whole lot stupid. :|

*****
For the first problem, from what I understood, the sorting should have been done after all values have been inputted.
So, instead of the add → sort → add → sort thing,
I think what was being asked for is mainly just the sorting function.

Given an input sample: 2 8 63 32 98 0
The void function should have been able to rearrange that to 2 8 32 63 98 when called from main.


      
  m y . L i F E . i . t r a d e . i n . f o r . y o u r . P A i N .

Re: Linked Lists
Link | by Lanster on 2008-11-16 05:13:16 (edited 2008-11-17 06:45:32)
*speechless*

......................................
What should I do???//confused

Anyway...
here the logic for the 'change()'
I'll use selection short

We need a "help" and "help2" pointer to do it

(note : pointer == cursor)

1. search the data that have the lowest value
2. change it with the first value

you know about selection shorts, aren't you???

to change it, for example 12 - 13 - 0 - 57
become 0 - 13 - 12 - 57

first search through the links list to search which container that contain the lowest value of data
help = help2 = head
while(help2-> next -> data > help->data) help2 = help2 -> next

then call function change()
logic :

cursor head and help is pointing to data 12
cursor help2 is pointing to data 13

then

if(help == head) head = help2->next // to save head cursor
help -> next = help2 ->next->next // to point the next cursor of help to data 57
help2 -> next -> next = help ->next // to point data 0 next cursor to data 13
help2 -> next = help // to point data 13 next cursor to data 12
// so data 12 will replace data 0




Uh, I just remember that you mention void short(node type **head), add, delete, search
I can't explain it now, I need to draw the visual logic
maybe I'll draw it later, I still have a lot of homework to do >.<
Sorry

-edit-
And I'm sorry for my crappy drawing
linklist

Reinforce

Back | Reverse | Quick Reply | Post Reply |

Copyright 2000-2025 Gendou | Terms of Use | Page loaded in 0.0009 seconds at 2025-07-14 13:49:00