If you think inserting and deleting with arrays is easy, just wait till you see what happens in a linked list. Since all the nodes in a linked list are distributed through the computer's memory, you don't have to shift anything, no matter where you insert an element. All you have to do is find the nodes on the left and right of where you want to insert your new node. That's it.

Let's start with this list:

 

If you want to insert from the beginning (giving it a new head like the Hydra), just

1. connect the next variable of your new head to the old head.
2. reassign the head pointer to the new head.

 

If you're working with a doubly-linked list, you'll also want to connect the previous variable of the old head to the new head and set the new head's previous to null. You'd still move the head variable, though.

 

The trick? You can't do this process in reverse order. If you try connecting the head pointer and then change the next/previous pointers, you'll lose the list before you get the chance to add the value on.

If you wanted to start over, mission accomplished. Otherwise…you've got a problem.

Since head points to the new head, which isn't connected to anything else yet, you don't have a way of getting to the old head (much less the rest of your list) anymore.

 

If you have a doubly-linked list, you can just walk backwards and recover the list, but in a singly-linked list those values are gone.

[Gulp]

To delete the head, you have two options. If you don't need to do anything with the deleted value, just move the head pointer over one value. If you need to use that value you're deleting for something, you'll want to assign it to a temp variable before moving the head.

 

Once temp has taken over holding the old head's place, you can move head to the new head, which is—wait for it—temp's next variable.

 

If the list is doubly linked, set the new head's previous value to null.

 

Do whatever you want with that old head, and then delete the temp reference entirely. No more head.

…Okay, there's still a head, but it isn't the same head as before. You get what we mean.

 

Inserting or deleting at the tail is about the same, except you're working with the end of the list.

To insert, all you need to do is set the tail's next to a new node before setting that new node as the new tail.

 

If the list is doubly linked, you'll also need to set the new node's previous pointer to…the old tail. Once all the pointers are taken care of, just reset the tail pointer to the new node.

 

Done. Please, hold your applause till the end of the guide.

To delete the tail, you'll have a much easier time when working with a doubly-linked list. Again, set a temp variable to the tail, then move the tail to the old tail's previous pointer. Once you have it pointing at the previous node, set the next value to null. Your list is officially shaved off one value.

Singly-linked lists? They're a little stickier. Create that temporary node reference, but this time set it to equal tail.

 

Once you've found the tail and set temp to it, walk down the list from the head to tail, until you find the next pointer that equals tail.

 

Set the tail equal to the node with its next value as the current tail, then set that new tail's next to null.

Easy-peasy.

 

Do whatever you want with the old tail, or just delete it. It doesn't really matter to us.

The toughest operation, though, is inserting or deleting from the middle of a list. Compared to an array, it isn't too bad, but still.

First step: find the spot you want to insert or delete from. You should have two nodes: the one that comes before the new node and the one that comes after. If you're inserting a node, connect the new node's next to the node it should point to (4) before changing next on the node it should come after (2). That way, both nodes point to the same node.

 

The list is doubly linked, you'll also want to set the new node's previous pointer to the before node.

 

Then set the before node's next to the new node. Now you've got another link in the chain.

 

Deleting's a similar process, except you'll need to create a temporary variable (but what else is new?).

 

Then set the next of the node that comes before to the node that comes after (and set the previous in the opposite direction of things that are doubly-linked).

And…you're done. Do whatever you want with that temp variable; the node's no longer connected to the list, since none of the nodes can reach it anymore.

 

What about inserting and deleting from stacks and queues? Better buckle up first. It's gonna be a bumpy (but fun) ride.