# Lists Overview Credit to Justin Shin (UTA Fall '23)! **List:** an ordered sequence of items. Fundamental operations on lists include adding elements, accessing elements at a specific index, removing elements, and checking whether a specific element is in a list.&#x20; ## **Immutable vs Mutable Lists** What is the difference between an **immutable list** and a **mutable list?** Let’s say that you have a list called myList. You want to add an element to myList. - For **mutable lists**, if you add an element to myList, the new element is present inside of myList. - For **immutable lists**, if you add an element to myList, the original myList will remain the same, but a new list containing the new element will be returned. :::info Here's an example of some Java-style pseudocode that highlights the difference between mutable and immutable lists. ```java public void example() { // mutable list example MutableList<Integer> mutList = new MutableList<Integer>(); mutList.add(5); mutList.add(6); // now, mutList is [5, 6] // immutable list example ImmutableList<Integer> immList = [5, 1, 7]; ImmutableList<Integer> newList = immList.add(10); // immList would remain [5, 1, 7], but newList would be [5, 1, 7, 10] } ``` ::: - **TLDR:** Mutable lists are good when you want to make a permanent change in the data. Immutable lists are good when you want to make a temporary change, such as when you are exploring a possible scenario (i.e., Decision Tree). _When do you want a mutable list?_ You want a mutable list when you have to access the same list in two different spots in your program because you want the changes through one to be visible through the other. (e.g., a shared calendar or a shared to-do list) _When do you want an immutable list?_ When you want to make temporary changes to a list, you should use an immutable list.&#x20; _If a list is mutable but we want to make a temporary changes, what do we do?_ You should **make a copy of the list**. Make a temporary change in the copy which will leave the original, mutable list untouched. - This is what happened in **Decisions Tree**, while our main attribute list was a mutable list, we needed to make a copy of the attribute list (which makes it an immutable list) so that we could make temporary changes on one side of the decision tree and then traverse through the other branches of the tree with the original untouched list. ## **Arrays vs Linked Lists (Chains of Nodes)** _What is the main difference between Arrays and Linked Lists when it comes to memory?_&#x20; _LinkedLists:_ - In Linked Lists, elements are organized as a collection of nodes, each node connected by a reference to the next node (there could also be doubly-linked lists where there is a previous reference to the previous node) - These nodes are scattered around in memory—NOT in consecutive slots. - All in all, linked lists are more efficient than arrays when it comes to memory allocation. Unlike arrays, the size for a linked list is not pre-defined, allowing the linked list to increase or decrease in size as the program runs. _Arrays_: - Arrays are organized in consecutive slots in memory. Think of this as a contiguous row of blocks that contain values and are indexed from 0, 1, and so on. _When should you choose a Linked List vs Array and vice versa?_ **Main Conclusion**: the primary consideration is based off what operations on the list that you want to do most frequently. - If you want to do a lot of list operations that depend on the specific position of an element in a list, then an Array might be a better option (ex: example could be a stadium manager where you already have access to the seat numbers corresponding to the index of an array that would be used to manage the seats) Additionally, an array may prove useful in the case where you know exaclty how much space you need. (ex: if you were storing the names of students living in a four person suite, you would never need an array bigger than 4) - If you need to do a lot of addition and removal of elements without having to worry about immutable vs mutable lists, or you aren’t worried about the specific location of elements in memory, or don't want to worry about predefined size constraints, then a Linked List might be better (i.e., if your program has to deal with the removal/addition of a lot of different elements, a Linked List would be better) **Note**: Make sure to understand the different in time complexities between the Array and the LinkedList (i.e., get, remove, add).  **\[1]**: - **Amortized Constant** means that we judge time complexity based off the average of multiple operations of an algorithm, not just one operation. - The reason why add first/last is amortized constant is because when the array runs out of space, we double the size of the array which would be linear time because have to change the array from n positions to 2n positions. - However, inserting an element into an array takes constant time, so the majority of the time, adding an element into an array is constant time. Therefore, if you take the average of all the time costs of adding an element to an array, it would be amortized constant because doubling an array (linear time) doesn’t occur too often when compared to just inserting an element into the array (constant time). **\[2]**: What assumption do we have to make about the references of a node that we want to remove? - We have to assume that the node contains both a reference to the next node and the previous node in the Linked List. Then, we can just call **bypass()**. - If there is not a previous node, then there would be a linear cost to find the node previous to the current node that you want to remove. *** _Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CSCI0200 document by filling out the_ [_anonymous feedback form_](https://docs.google.com/forms/d/e/1FAIpQLScDfGq8uaR2zXSc9wZTA83kfmM8N9UATB0RU0cGMfvJnmL5lQ/viewform)_._