https://i.imgur.com/QCBFJbn.png

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. ![Singly linked list](https://steemitimages.com/DQmYNVQ14sSpKbJ6iq3ei6j5uJV5AvZeaEutKvZdfCD3is6/2017-07-27%2009_34_24-VisuAlgo%20-%20Linked%20List%20(Single%2C%20Doubly)%2C%20Stack%2C%20Queue%2C%20Deque.png) 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. ```java public class ListNode { int val; ListNode next; ListNode (int val) { this. val = val; } } ``` Sometimes you want to use a wrapper, like this: ```java 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: ![Doubly linked list](http://www.eng.utah.edu/~cs2000/Assignments/assignment10/assignment10e.gif) 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 ```java 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 ```java 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: ```java 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!