Rubenerd

One of the things I've had to relearn in Java after not touching it for a while in a university setting is not the concept of linked lists specifically, but how they're implemented. Despite Java having native support for them in its API, we're expected to create our own Linked List objects to use in our programs, presumably to demonstrate we understand the concept and so we could create a really long linked list of grilled cheese sandwiches.

As I understand it in an abstract sense, each node in a linked list contains an object and a pointer to the next node if applicable. The header points to the first node, and the last node points to null. To load in all the nodes we'd traverse the linked lists starting at the head until we encountered a null.

In a similar way to a primitive array with shifting, a linked list is expected to be able to have nodes removed and added from any arbitrary position including at the head and the end.

Adding nodes to a link list

Adding nodes entails traversing the linked list until we come to the node just before where we want to insert our new node. We then point the previous node to our new one, and our new node to the next in.

To add the node to the beginning, we don't need to traverse the list, we just point the header to the new node, and our new node to the previously first node.

To add the node to the end, we traverse until we reach a null value, then have the last node point to our new node, and our new node point to null instead.

Removing nodes

Not surprisingly, removing nodes entails the opposite of adding them. Instead of severing links to place a new node, we sever the nodes between the node to remove and the nodes surrounding it, then link the surrounding nodes. If your programming language doesn't have garbage collection, you'll then want to undefine the object.

If the node is at the beginning we link the header to the next node on the list, and if the node is at the end we take the second last node and point it to null.

Observations

Linked lists (and binary trees etc) are a classic example of a concept which seems perfectly simple when you explain it, but I imagine if you don't plan it and understand it properly you could make a huge mess of it when it comes down to coding. Like deciding to make a grilled cheese sandwich with pop tarts and chocolate ice cream instead seems like a great idea in theory, but you end up setting your toaster oven on fire.