Understanding Arrays and Linked Lists in Computer Science
Arrays and linked lists are fundamental data structures in computer science. Arrays provide a fixed-size collection, while linked lists offer dynamic sizing. Arrays are efficient for accessing elements but can be inefficient for insertions and deletions. Linked lists, on the other hand, allow for easy insertion and deletion at the cost of access efficiency. Each structure has its advantages and disadvantages, making them essential concepts for understanding data organization and manipulation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Arrays and Linked Lists "A list is only as strong as its weakest link." -Donald Knuth
Static vs Dynamic Static data structures Arrays. Fixed, predetermined capacity. If full, have to allocate more space and copy values into that space. Dynamic data structures Linked structures, like linked lists and trees. They grow / shrink one element at a time. Avoid some inefficiencies of static containers. CS 221 - Computer Science II 2
Efficiency of Array Operations Big-O of Array Operations To insert element at beginning of an array? Space available? No space available? While maintaining relative order? To insert element at the end of array? To insert or delete an element in the middle of the array? To access the kth element? CS 221 - Computer Science II 3
Advantages of Arrays Used to represent multiple data items of same type by using only single name. Can be used to implement other data structures like stacks, queues, trees, graphs, etc. 2D arrays are used to represent matrices. CS 221 - Computer Science II 4
Disadvantages of Arrays Array is static structure, has fixed size. Must know in advance that how many elements need to be stored. If allocate more memory than required, the memory space will be wasted. If we allocate less memory than required, it will create problem. Elements of array stored in consecutive memory locations, so insertions and deletions are time consuming. CS 221 - Computer Science II 5
Single-Linked List Single-linked list is implementation-dependent data structure. Not defined by set of core operations. Have to understand how to manipulate nodes. Each node stores reference to element in linked list. Nodes also maintain references to next node in the list. Create new node when add new element to list. Remove node when element is removed from list. Allow garbage collector to reclaim that memory. CS 221 - Computer Science II 6
Anatomy of Single-Linked List A linked list consists of: Sequence of nodes, can change during execution. Successive nodes connected by node references. Last node reference points to null. Grows / shrinks during operation. Not limit number of elements. Keep references to first / last (optional) nodes in list. head tail A B C null pointer CS 221 - Computer Science II 7
Terminology Node s successor is the next node in the sequence. The tail (last node) has no successor. Node s predecessor is the previous node in the sequence. The head (first node) has no predecessor. List s size is the number of elements in it. A list may be empty (i.e. contain no elements). CS 221 - Computer Science II 8
Single-Linked List Operations Inserting New Elements Inserting at beginning of list Inserting at end of list Inserting into middle of list Deleting Elements Deleting element from the beginning of list Deleting element from end of list Deleting element from middle of list Traversing List CS 221 - Computer Science II 9
Insertion: At Beginning Steps: 1. Create a new node with new element. 2. Connect new node to list. 3. Update head and count variables. Special Case: if empty Same steps but have to update tail. CS 221 - Computer Science II 10
Insertion: At Beginning General Case: One or more elements in list. 1. Create a new node with new element. newNode 3 count D head tail A B C CS 221 - Computer Science II 11
Insertion: At Beginning General Case: One or more elements in list. 2. Connect new node to list. 3 count newNode head tail D A B C CS 221 - Computer Science II 12
Insertion: At Beginning General Case: One or more elements in list. 3. Update head and count variables. 4 count newNode head tail D A B C CS 221 - Computer Science II 13
Insertion: At Beginning Special Case: Empty list. 1. Create a new node with new element. 2. Connect new node to list. newNode 0 count D head null tail CS 221 - Computer Science II 14
Insertion: At Beginning Special Case: Empty list. 3. Update head and count variables. 4. Update tail. Extra Step newNode 1 count head tail D CS 221 - Computer Science II 15
Insertion: At End Steps: 1. Create a new node with new element. 2. Connect list to new node. 3. Update tail and count variables. Special Case: if empty Most of same steps but can t connect list to new node and have to update head. CS 221 - Computer Science II 16
Insertion: At End General Case: One or more elements in list. 1. Create a new node with new element. newNode 3 count D head tail A B C CS 221 - Computer Science II 17
Insertion: At End General Case: One or more elements in list. 2. Connect list to new node. 3 count newNode tail head D A B C CS 221 - Computer Science II 18
Insertion: At End General Case: One or more elements in list. 3. Update tail and count variables. 4 count newNode tail head D A B C CS 221 - Computer Science II 19
Insertion: At End Special Case: Empty list. 1. Create a new node with new element. 2. Can t connect list to new node, because tail is null. Remove Step newNode 0 count D head null tail CS 221 - Computer Science II 20
Insertion: At End Special Case: Empty list. 3. Update tail and count variables. 4. Update head. Extra Step newNode 1 count head tail D CS 221 - Computer Science II 21
Deletion: At Beginning Steps: 1. Remove deleted node from list, have to use temporary variable. 2. Update head variable. 3. Update count variable. Special Case: if only one node left Most of same steps but don t need temporary variable and have to update tail. CS 221 - Computer Science II 22
Deletion: At Beginning General Case: Two or more elements in list. 1. Remove deleted node from list, have to use temporary variable. 4 count next head tail A B C D CS 221 - Computer Science II 23
Deletion: At Beginning General Case: Two or more elements in list. 2. Update head variable. 4 count head next tail A B C D CS 221 - Computer Science II 24
Deletion: At Beginning General Case: Two or more elements in list. 3. Update count variable. 3 head count next tail B C D CS 221 - Computer Science II 25
Deletion: At Beginning Special Case: One node left. 1. Remove deleted node from list. 2. Update head variable. 3. Update count variable. 4. Update tail. Extra Step 0 count A head null tail CS 221 - Computer Science II 26
Deletion: At End To delete last element, have to update link from node previous to last node. In order to update this link, have to traverse nodes to that node. CS 221 - Computer Science II 27
List Traversal Steps: 1. Initialize temporary variable to head. 2. Advance temporary variable until find element or position. CS 221 - Computer Science II 28
List Traversal 1. Initialize temporary variable to head. current tail head D A B C target 4 count CS 221 - Computer Science II 29
List Traversal 2. Advance temporary variable until find element or position. current tail head D A B C target 4 count CS 221 - Computer Science II 30
List Traversal 2. Advance temporary variable until find element or position. current tail head D A B C target 4 count CS 221 - Computer Science II 31
Deletion: At End Steps: 1. Use temporary variable to traverse nodes until reach node before last one. 2. Remove deleted node from list. 3. Update tail variable. 4. Update count variable. Special Case: if only one node left Most of same steps but don t have to traverse nodes and have to update head. CS 221 - Computer Science II 32
Deletion: At End General Case: Two or more elements in list. 1. Use temporary variable to traverse nodes until reach node before last one. 4 count current tail head A B C D CS 221 - Computer Science II 33
Deletion: At End General Case: Two or more elements in list. 1. Use temporary variable to traverse nodes until reach node before last one. 4 count current tail head A B C D CS 221 - Computer Science II 34
Deletion: At End General Case: Two or more elements in list. 1. Use temporary variable to traverse nodes until reach node before last one. 4 count tail current head A B C D CS 221 - Computer Science II 35
Deletion: At End General Case: Two or more elements in list. 2. Remove deleted node from list. 4 count tail current head A B C D CS 221 - Computer Science II 36
Deletion: At End General Case: Two or more elements in list. 3. Update tail variable. 4 count tail current head A B C D CS 221 - Computer Science II 37
Deletion: At End General Case: Two or more elements in list. 4. Update count variable. 3 count tail current head A B C CS 221 - Computer Science II 38
Deletion: At End Special Case: One node left. 1. Remove deleted node from list. 2. Update tail variable. 3. Update count variable. 4. Update head. Extra Step 0 count D head null tail CS 221 - Computer Science II 39
Advantages of Linked Lists Insertions / deletions don t require shifting. No wasted space. Size is not fixed, can be extended or reduced. Elements do not have to be stored in consecutive memory. CS 221 - Computer Science II 40
Disadvantages of Linked Lists Requires more space need references to successor and stored elements. No direct access to elements by position. To find a particular element, have to go through all those elements that come before that element. We can only traverse from the beginning. Sorting the elements stored in linked list are more difficult and inefficient. CS 221 - Computer Science II 41
