Latest Lists

How do Linked Lists work?

I'm just looking for a general summary on linked lists. I've been programming for a few years now, and Linked Lists utterly baffle me. I've googled it, read all the links, and checked out the API, but I still just don't get how they work. Can anyone please explain this in English?

Public Comments

1. Think of it as an open ended pearl necklaces. With each pearl represented by a group of data, such as grade, color, size, value etc. and the links as the pointers connecting them together, so that you can look at them one by one or sort them by their attributes. The linked list make it easier to manage some variable numbers of data groups as opposed to one dimensional array which has fixed length and not easily expended or reduced. Hope this helps.
2. The most basic kind of linked list is a singly linked list. In that case, each node has a pointer/reference to the next node in the list. A node is an object/struct that holds a single value in the list, as well as a pointer to the next node. By having each node point to the next node, it creates an ordered list. Also each list has a pointer to the head of the list, or the first element. The head pointer can be null if the list is empty. Imagine a bunch of people standing in a room. You go to bob and tell him, remember your value is 1, and the next person is frank. Now you go to frank, and tell him, your value is 10, and the next person is mike. Then you go to mike and tell him, your value is 3, and you are the end of the list. So in this case each person (knows) their own value and who the next person in the list is. All of them together form a list. class Node{ int value; Node * nextNode; } class LinkedList{ Node * head; Node * tail; void add(int value){ .....Node * current = new Node(); .....current->value = value; .....if(head == null){ ..........head = current; ..........tail = current; .....} .....else{ ..........tail->next = current; ..........tail = current .....} } } So imagine a linked list that contains head-> [ 1 4 8 9 ] <- tail . At this point, head points at the node containing the 1, and the tail points at the node containing the 9. The node containing the 1 also has a pointer to the next node in the list, in this case the node containing the 4. The 4 points to the 8 and so on. No imagine I call the add(3) function that I have above. ..........tail->next = current; This line will cause the node containing 9 to point to the new node that now contians the 3. ..........tail = current this moves the tail, as the tail always points to the last node in the list. The result is: head-> [ 1 4 8 9 3 ] <- tail Really the best way to really understand any data structure is to code one your self. I'll guarantee if you code one it will make a whole lot more sense to you. Start out with a lingly linked list withe a head and a tail, then turn it into a double linked list (pointer to previous node too). When you are trying to figure out how to move pointers around in inserts and deletes, draw it in a white board just like the code is doing, it helps a bunch.
3. A linked list is an Abstract Data Type. It works because of the structure of the program. The program manages the pointers for you. Let's clarify the definition of a pointer. Node node = new Node(); node is the pointer. Node() is the call to the mechanism to assemble from custom instructions. 'new' is a reserved word that commands memory heap to reserve space in memory for an Object of type Node. Without linked list, we would have to have unique pointers. eg, node1, node2... node99; or, we would have to make an array Node [] nodes = new Node[ 99 ]; But that approach is disadvantageous because we must track the pointers. This is disadvantageous because to add or subtract an Object of type Node becomes very complex to do with code. Therefore, the LinkedList. The structure does it all. In a simple LinkedList we always start with the first Object and process until the end. The other condition is the list must be sorted. Node is an arbitrary but descriptive naming. Here is the essentials. class Node { String value; Node next; Node previous; // methods to set-get next, previous and value } We see that next and previous are pointers to identical types of Objects. We utilize another program to maintain the datastore -- LinkedList of Nodes. All we care about here is that a single node is pointed to and it has the label head class NodeList { private Node head; // methods here will a) start a list if we are empty; b) if we have a list in progress, insert a new Object in the proper sequence; c) if we have a list in progress, search the list looking for a match to delete. // an example method to search for private Node getNode( Node searchFor) { Node runner = head; if( runner.value.equals( searchFor.value ) return runner; else runner = runner.next; Maybe you can see, we carefully code swapping of pointer names and by doing so we can express the data algorythm in simple naming conventions.