Understanding Linked Lists: Adding Elements for Beginners

[muna580]

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?

 

[Hurkyl]

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]

I think the best way to understand a linked list is to become acquainted with Lisp. Specifically, I worked through most of http://mitpress.mit.edu/sicp/full-text/book/book.html.

 

[muna580]

I think the best way to understand a linked list is to become acquainted with Lisp. Specifically, I worked through most of http://mitpress.mit.edu/sicp/full-text/book/book.html.

The book you should me, is that Java? I cna't find the chater with LInkedList.

 

[verty]

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]

How do I do a window there the user selects "true" or "false"?

 

[chroot]

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-]

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]

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]

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? Let's 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 let's 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.