Linked List


by muna580
Tags: linked, list
muna580
#1
Dec3-06, 02:36 PM
P: n/a
I don't understand the concept of linked list. I mean, I do understand it, but I don't understand how to add something to a linked list. I know there are three diffrent ways to add, one is to the front, the other one is to the back, and the last one is anywhere. But I don't understand howt o do this. Like can I get a sample code?
Phys.Org News Partner Science news on Phys.org
Internet co-creator Cerf debunks 'myth' that US runs it
Astronomical forensics uncover planetary disks in Hubble archive
Solar-powered two-seat Sunseeker airplane has progress report
Hurkyl
Hurkyl is offline
#2
Dec3-06, 02:43 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
It's always better to work out the detail yourself. One process I try to suggest is to do this:

You want to add something to the head of a linked list.

So, suppose you had a "real-life" linked list. (Say, a piece of paper with a bunch of boxes and arrows, or maybe a bunch of blocks tied together with a bunch of strings)

Write down, in excruciating detail directions for adding something to the head of the list -- you want directions that a 10-year old could follow.

At that point, it's usually just a matter of literally translating your directions into actual code.


Anyways, if you want answers, you could try Wikipedia
verty
verty is offline
#3
Dec3-06, 02:53 PM
HW Helper
P: 1,373
I think the best way to understand a linked list is to become acquainted with Lisp. Specifically, I worked through most of this book.

muna580
#4
Dec3-06, 03:02 PM
P: n/a

Linked List


Quote Quote by verty View Post
I think the best way to understand a linked list is to become acquainted with Lisp. Specifically, I worked through most of this book.
The book you should me, is that Java? I cna't find the chater with LInkedList.
verty
verty is offline
#5
Dec3-06, 03:13 PM
HW Helper
P: 1,373
They just call it a list. It sounds like that would be difficult to follow, so I think Hurkyl's suggestion is best. If you just look for Java source code, I don't think you will understand the reasons behind it.

Let me ask a quick question, how would you join two linked lists together?
muna580
#6
Dec3-06, 03:48 PM
P: n/a
How do I do a window there the user selects "true" or "false"?
chroot
chroot is offline
#7
Dec3-06, 04:10 PM
Emeritus
Sci Advisor
PF Gold
chroot's Avatar
P: 10,424
Quote Quote by muna580 View Post
How do I do a window there the user selects "true" or "false"?
GUI programming varies tremendously with the language and toolkit you're using. There is no single way to do this.

- Warren
-Job-
-Job- is offline
#8
Dec3-06, 04:28 PM
Sci Advisor
-Job-'s Avatar
P: 1,132
A linked list is like a chain of paper clips. Each clip storing some value. Each clip knows what clip comes after it. Your program grabs the chain of clips at one end, called the head clip. If you want to insert a clip at the top then you connect the clip on top of the head clip, and make that the new head clip.
If you want to insert at the bottom, then you just connect the clip on the tail end of the chain.
If you want to insert in the middle, say after a specific clip, you start at the head and come down through chain until you find the clip after which you want to insert, disconnect the chain at that point, insert your clip, and then append the rest of the chain after your new clip.
Sane
Sane is offline
#9
Dec3-06, 05:11 PM
P: 223
Quote Quote by verty View Post
Let me ask a quick question, how would you join two linked lists together?
Traverse through the first linked list to find the tail. Then point that node to the head of the second list.


To the original poster, I'd suggest what others have been saying. Read lots. But experiment even more. I remember linked lists being easiest to understand by testing different ideas. What your brain is able to discover on its own, beats a book any day.
haki
haki is offline
#10
Dec4-06, 03:38 AM
P: 162
Each different data structure has a specific strength and weakness. That is why there is not a single data structure but we have quite a few different ones and a few different categories of them, namely you have Lists (order of elements matters, can have duplicates), Set (order of elements does not matter, cannot have duplicates), Map (stores ordered pairs (Key, Value), keys are unique, cannot have duplicate keys) and finally Queue (usually you add elements only to the back, and take elements either from the back or the front, generally you have 2 kinds of queues FIFO and LIFO, that would data structures in a nutschell.

What is the purpose of LinkedList?

Notice it is a List, soo you have a "list" of elements where their order matters and you can have duplicate entries(same value at different locations).

Are you familiar with arrays? Lets say you would like to make a list of your favorite bands

String[] favBands = {"U2","Franz Ferdinand","The Killers","The Strokes"};

notice this is just an array, you cannot add new entries or delete them but you can change them e.g.

favBands[1] = "The Divine Requiem";

but for the list data structures, you want to be able to

add entries at any particular location
delete entries at any particular location
change entries at any partucular location

Are you familiar with ArrayList or his older brother Vector?

It is a list that uses an array to store entries. But notice

when you add an entry let say at the middle what has to be done? You have

0:"U2"
1:"Franz Ferdinand"
2:"The Killers"
3:"The Strokes"

to add an entry at the middle let say at position 2, we need to allocate a new array with the size of current elements + 1, copy first the elements before the insertion point, put in the new element and copy the rest of the elements. That is what ArrayList does because of that reason you have the optional parameter of setting the initial size of the array e.g.

ArrayList<String> favBands = new ArrayList<String>(100);

now the favBands will expect that we add 100 entires soo if we will be adding to the end of the arraylist it will not make a new array until we want to add 101st element. Ofcorse if we put 50 elements and try to insert lets say in somewhere in the middle(position 25) it will have to do some copy work.

Soo adding in the middle or at the front is not very recommended using ArrayList. Same goes for removing elements.

For that reason there is LinkedList it enables efficient insertion and removal of elemenets at any location including the front and the middle.

How is that achieved? Using Links. Each element knows which entry is in front of them and which entry is behind them. Soo if you want to add an entry you simply modify the links, the remove you do similar job. Soo there is no array behind the LinkedList that would need to be recreated and copied and stuff almost everytime you add an entry at an arbitrary position. But as any data structure the LinkedList has it drawbacks and that is to access an entry at a particular location let say get(25) will have to traverse all the links before the position to find it. Soo accessing the link at an arbitrary location is not very efficient at the LinkedList. Maybe you can try implementing your own ArrayList for starters and then LinkedList.

I would recommend the Big Java book by Horstmann it has 3 chapters on Data Structures that explain the basics and some more advnaced things of Data Structures.
Attached Thumbnails
LinkedList.png   LLAdd.png   LLRemove.png  


Register to reply

Related Discussions
Exception for doubly circular linked list Programming & Computer Science 17
Linked genes Biology, Chemistry & Other Homework 2
Problems with Linked List and pointers Programming & Computer Science 6
linked list help! Programming & Computer Science 1
Doubly Linked List Introductory Physics Homework 13