Interview Material: What's the deal with Linked Lists?

Hello!  I'm going to start a series on my blog (well, technically it will be all that's here as of now) where I go over a lot of the information one needs for a Software Engineering job interview.  My first post in the series will be going over Linked Lists, their uses and how to implement them in Java.  So, let's start then!

What exactly are Linked Lists, you say?

In computer science, there are many abstract data types that are used to store and access data.  One of these numerous abstract data types (which will be referred to as ADT from now on) is a Linked List.  A Linked List is a pretty fundamental concept that most applicants should understand.  The structure is pretty simple and can be summarized in a bullet-point list:

• A collection of "nodes" that point to each other, where the last node points to NULL
• Usually, the structure comes in 2 types, a singly linked list or a doubly linked list
• Singly linked lists only have one entry point, and it's usually the "head" (or first) element
• Usually, each node only points to the next node
• Doubly linked lists have a head and a tale element so the list can be accessed from either side
• Each node can point to the previous and the next one, allowing you to traverse the list from the tail
• Inserting takes O(1) time for doubly linked lists or O(n) time for singly linked lists, while inserting in place takes O(n) time.
• Likewise, deleting the head (or tail in a doubly linked list) takes O(1) time while deleting in place is O(n)
• Searching the structure for a node takes O(n) time
• Memory-wise, the structure only takes up roughly O(n) space.

Alright, so let's discuss these runtimes.  To have an example on hand, we'll use the following diagram as a representation of a singly linked list.  Please not that the bolded integer is the head and the arrows are pointers to the next node.

5 -> 4 -> 11 -> 32 -> 2 -> 15 -> 4 -> NULL

First, I mentioned insertion.  Insertion's runtime is all based on the linked list's implementation.  If the implementation uses a tail node (doubly linked list), then insertion is just pointing the tail node to the new node and then swapping them.  This should take constant time.  To insert a node in a singly linked list, the structure has to go through all of the nodes until it gets to null and then appends the new node.  This would obviously be in O(n) time.

Next, I mentioned deletion.  Deletion's runtime is O(1) because it usually is implemented as removing the head or tail node, which would be O(1) time.  To accomplish tail-end deletion, you would write a function that points the tail node's previous node's next node to NULL (say THAT 10x fast!).  Though, deletion of a certain node would involve traversing to that node in the list, and then set the previous node's next node to its next node's next node.  Yeah.  Head hurting yet?  Here's sample code on how to delete a specified value:

public Node deleteNode( Node head, int data) {
Node n = head;
if (n.data == data) {
return head.next; //Return LL without head node
}
while (n.next != null) {
if (n.next.data == data) {
n.next = n.next.next; //Delete n.next, which is the node we want
return head;
}
n = n.next;
}
return head;
}

Now, we went over a bit of searching in the code up there.  If you remember, I noted that it's runtime is O(n).  If you see how we traversed the linked list above, you would notice that we have to go to every node looking for a certain value. The worst case scenario in searching an n-long list for a value d is that d is at the end.  That means we would have to go through the entire length of the list, which means search is dependent on the length of the list.  Therefore, search is O(n).

Great, I understand how to implement one, but why?

Linked lists aren't inherently useful, themselves, but are useful in implementing other data structures.  Both stacks and queues are often implemented using linked lists as their underlying structures.  Also, a hash table can use a linked List to store the chain of items associated with the same hash value.  Please note that these are just a few example usages of linked lists and are hardly the only use cases!

I realize I haven't implemented the entire class for a linked list, but I promise I'll upload the code soon!  I'm trying to figure out how to upload code to Blogger without it looking insane, so hopefully there's a solution and it'll be up soon!  Thanks for reading my first post, I hope to have many more soon!