Understanding Linked Lists: Adding Elements for Beginners

  • Thread starter muna580
  • Start date
  • Tags
    List
In summary, a linked list is a data structure that stores elements in a chain-like structure where each element points to the next element. This allows for efficient insertion and removal of elements at any location in the list. It is important to read and experiment with linked
  • #1
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?
 
Technology news on Phys.org
  • #2
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
 
  • #3
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.
 
  • #4
verty said:
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.
 
  • #5
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?
 
  • #6
How do I do a window there the user selects "true" or "false"?
 
  • #7
muna580 said:
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
 
  • #8
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.
 
  • #9
verty said:
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.
 
  • #10
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.
 

Attachments

  • LinkedList.png
    LinkedList.png
    6.8 KB · Views: 454
  • LLAdd.png
    LLAdd.png
    11.8 KB · Views: 490
  • LLRemove.png
    LLRemove.png
    10.4 KB · Views: 483

1. What is a linked list?

A linked list is a data structure that consists of a sequence of nodes, each containing a piece of data and a pointer to the next node in the list. Unlike arrays, linked lists do not have a fixed size and new elements can be added or removed easily.

2. How do you add elements to a linked list?

To add elements to a linked list, you first need to create a new node containing the data you want to add. Then, you can insert this node at the beginning, end, or any desired position in the list by updating the pointers of the adjacent nodes accordingly.

3. What is the time complexity of adding elements to a linked list?

The time complexity of adding elements to a linked list varies depending on the position of the insertion. If the element is added at the beginning or end of the list, the time complexity is O(1). However, if the element is added at a specific position, the time complexity is O(n) as it requires traversing through the list to find the correct position.

4. What are the advantages of using a linked list?

One advantage of using a linked list is its dynamic nature, as it allows for easy addition and removal of elements without the need for resizing. Another advantage is its efficient use of memory, as it only requires enough memory to store the data and the pointers to the next node, unlike arrays which require a fixed amount of memory.

5. How do you handle errors when adding elements to a linked list?

When adding elements to a linked list, it is important to handle potential errors such as trying to add an element at an invalid position or adding a duplicate element. This can be done by implementing error handling mechanisms such as conditionals or try-catch blocks to ensure the integrity of the list is maintained.

Similar threads

Replies
9
Views
942
  • Programming and Computer Science
Replies
16
Views
1K
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
3
Views
268
  • Programming and Computer Science
Replies
15
Views
1K
  • Programming and Computer Science
Replies
26
Views
6K
  • Programming and Computer Science
Replies
2
Views
2K
  • Programming and Computer Science
Replies
20
Views
5K
  • Programming and Computer Science
Replies
4
Views
3K
  • Programming and Computer Science
Replies
5
Views
1K
Back
Top