A Linked List is a sequence of nodes that are connected bylinks with a header at the beginning. Itis a linear data structure where each element or node is a separate object.Every node has a single element which can be a value or an object. Each node apartfrom the last has a successor after it. A linked list doesn’t have a fixedamount of nodes, meaning that it can grow and shrink. This is good because youmight have an unknown amount of objects you have to deal with in a program, butby using a linked list means you don’t have to worry about the size. However,by using a linked list, you can’t get direct access to an individual elementwithin the list.
You must start at the head of the list and follow thereferences until you get to the item you want. There are three different types of linked lists:· SinglyLinked Lists are a sequence of nodes connected by links that only goes inone direction, meaning that you can’t go back to the previous node. Each SSLnode contains an element as well as a link to the next node or a null link ifthe there is no successor. The header in a SLL will have a link to the firstnode in the linked list.· DoublyLinked Lists are similar to singly linked lists, but they have tworeferences, one for the next node and one for the previous node meaning thatyou can go in either direction: forward or backwards. · CircularLinked Lists will link the last node back to the head of the list (firstnode).Array List is a child class of AbstractList and itimplements the List interface.
They support dynamic arrays that can grow asneeded. A normal array can’t grow or shrink as they have a fixed length whenthey are created. For an array you need to know how many elements are to beheld in it beforehand, while, in an array list, you create it with an initialsize but if it is exceeded, it will automatically enlarge the list. If an elementis removed, the array can also be shrunk. Array lists use arrays for internal storage which means thatit is fast for accessing elements because it implements the random accessinterface so it can go right to an element with the index to access it.Compared to a linked list, an array list is a lot faster in terms of randomaccess as linked list does not implement the random access interface and has totraverse through the whole list until you reach the right element.
Although itis slower, linked list can go either backwards or forwards so if you had toreach element 99 in a list of 100, then you can traverse backwards to get tothe 99th element. It does a sequential scan but this scan is veryslow. Adding and deleting elements at the head or middle of anarray list is slow and takes more time as the elements are being stored in multiplememory locations and that the elements that come after the point in which youare inserting or deleting will need to be copied forward or backward.
Linkedlists are faster for this because you would only need to update the next andprevious pointers of a node, making it more efficient in terms of speed.However, if you were to add to the end of the list, then an array list isfaster for this. Computational complexity of an algorithm is the amount ofresources that is needed in order to run it.
Although the resources are exactlyspecified, it is usually how much time is taken to run the algorithm and thisis known as time complexity. The time needed depends on the computer that isbeing used but the time is usually expresses as the number of needed elementaryoperations, which takes a constant time on one computer, and to change by aconstant when the user changes computer. Another way that resource can bedefined in this instance is space complexity which is the size of the memorythat is needed to run the algorithm. An algorithm is efficient if the values ofa function that tests these complexities are small. The computational complexities of the access, insert anddelete algorithms would mainly be time because for an application or program,you would want to be able to retrieve an item from the list as quick aspossible and with as little delay as possible. Space complexity would also beimportant but not so, compared to time as memory can be reused but we expectcomputation to get faster.
It has no benefit if it takes extremely long tosolve a problem. To summarise, array lists are better than a linked list ataccessing an element in a list as the array index gets you to that element,while in a linked list you must go through every node first until you get tothe right element. Linked lists are usually better than array lists when itcomes to inserting or deleting anywhere in a list. For example, linked listsare better for inserting or deleting at the beginning of a list because it hasa simple growth pattern where it either adds or removes nodes when it isneeded, but for an array list it must make a copy of the elements that followeither forwards or backwards. Linked lists are also better for inserting ordeleting in the middle of a list but would take more time as it must searchthrough the list to get to the point of insertion or deletion. Once the searchfor point in the list is done, the speed in which it inserts or deletes wouldbe similar to inserting or deleting at the start. However, linked lists can betime consuming if you were to insert or delete at the end of the list and thelast element is unknown but in an array list, the algorithm runs quite fast forinserting and deleting at the end.