While currently studying data structures and algorithms, I thought this would be a good place to "think out loud" and possibly help others along the way. I have been working on understanding Singly Linked Lists and here is what I have learned when it comes to building a Node class and a Singly Linked List class. Feel free to share your corrections if I get anything incorrect.
A Singly Linked List is a linear data structure. It is composed of nodes; each node points to the next node while the last node points to null. Unlike arrays, Singly Linked Lists are non-contiguous in memory, so new nodes can be added wherever there is space in memory. Arrays are contiguous in memory so the elements must be stored right next to each other. Arrays have a fixed size. In order to add elements to an array, you must copy all the elements into another place in memory with more space. Also, Singly Linked Lists are good at insertion and deletion at the beginning (the head), and insertion at the end (the tail). It takes fewer operations to do this, so the time complexity is O(1) constant time. However unlike arrays, Singly Linked Lists do not have indices, and random access of a node is not allowed.
My understanding of the Node class is that it builds the node's structure. A node is basically an object with a key/value pair: {value: value, next: null}. Nodes are connected via their next values. The next value points to the next node. Here is an example of a node pointing to the next node:
Here is an example of code for a Node class that constructs the node:
A Singly Linked List class builds the list's structure with the head, tail, and length. Here is an example of code for a Singly Linked List class that constructs the list:
Using these two classes, a Singly Linked List can be instantiated and built with nodes using the Node class. Within the Singly Linked List, various methods can be written to access and manipulate the list.
In the next part of this series, I will share what I have learned about adding nodes to the end of a list and removing nodes from the end of a list.
Top comments (0)