What is a linked list?

[cycledlinkedlist]

Hello! This is my first steemit post - welcome community!
I am a software engineer that worked at major software based institutions, and am here to teach you about computer science. Let's get started!

What is it?

Linked list is a basic data structure commonly used in computer programming in any language.
It consists of nodes, that are linked together. Each node has 2 attributes:

• some value that it stores, eg. a number, string etc.
• pointer/reference/you name it to next node

Each list has 2 special nodes (that could be the same one in case of linked list consisting of only one element):

• head - pointer to the first element of the list
• tail - pointer to the last element of the list. Its next pointer points to a null value. That way we know that this is the end of the list.

Let's visualize it.

Above lists consists of 6 nodes, with head being node with value 1 and tail node with value 6.

Linked list:

• is linear - meaning that it has a linear order (though it doesn't mean that its elements are adjacent in memory). Nodes are lined together.
• is ordered - meaning that list consists of elements which order is known. E.g. in above list, we know that node with value 1 is before node with value 2
• can have duplicate elements in terms of value - not like e.g. set. You can have one or more nodes that have the same value.
• elements can be sorted or unsorted. It doesn't handle sorting out-of-the-box like some other data structures such as binary search tree.
• elements are not indexed.

Differences to array

Those of you that are familiar with arrays already might notice that those data structures look similar.

What are the differences then?

1. Arrays let you retrieve elements in constant time O(1), since the elements are indexed. In linked lists, to retrieve element you have to start with the head and look for element checking if the value is the one that you're looking for. That takes linear time, O(n).
2. Linked lists might be more efficient when inserting elements. When you add a new element at the beginning of a list, it cost is constant O(1). However if the element should be added as the last one in the list, that will cost O(n), since you have to iterate over the whole list, and set tail's next value to that element. On the other hand, when adding element to an array it might be expensive - we need to create a space for inserted element, and shift other that are after it.
3. Linked lists also have dynamic size - you don't have to specify from the beginning, how many nodes the list will have. You have to do it in case of an array.

What is better then?

It depends on what circumstances you want to use it :-) Use above paragraph as a guide.

Definition in code

This is java implementation.

public class ListNode {
  int val;
  ListNode next;

  ListNode (int val) {
    this. val = val;
  }
}

Sometimes you want to use a wrapper, like this:

public class LinkedList {
  ListNode head;
}

Types of linked lists

In your interview or when solving tasks, when someone uses the term linked list usually what they mean is actually singly linked list described above.

You should know that there's also another type of linked list which is doubly linked list.
The difference between those 2 is that doubly linked list has 2 pointers: next and prev.
prev points to a previous element in a list.

Visualization:

Source: http://www.eng.utah.edu/~cs2000/Assignments/assignment10.html

Basic operations

Those could be the methods of previously mentioned LinkedList class.

Add

To the end of a linked list

public void append(int val) {
  if (head == null) { // if the list is empty, then we just set the head element.
    head = new ListNode(val);
    return;
  }
  ListNode current = head;
  while (current != null) { // iterate to the last element of the list. Linear time.
    current = current.next;
  }
  current.next = new ListNode(data);
}

To the beginning of a linked list

public void prepend(int val) {
  // We just need to change the pointers in that case. Constant time operation.
  ListNode newHead = new ListNode(val); 
  newHead.next = head;
  head = newHead;
}

Delete

This code will delete a node with a specific value:

public void deleteWithValue(int data) {
  if (head == null) {
    return; // nothing to delete, list is empty
  }
  if (head.val == data) { // if the element to delete is head
    head = head.next; // then we set a head as the next element, and it's done!
                      // deleting node is more like 'abandoning' node. You don't have to "destroy it"
    return;
  }
  
  Node current = head;
  while (current.next != null) { // iterate over all list elements
    if (current.next.val == data) { // if the value is found
      current.next = current.next.next; // then swich the pointers
      return;
    }
    current = current.next;
  }
}

Thank you for your attention!

Let me know if you want some linked list harder problems solving post!