DSA Chapter 3

linked lists

types of data structures to implement lists

• Static data structures

• Dynamic data structures

static data structures

• Defined and allocated before execution

• Size cannot be changed at the time of execution

• Array implementation of ADT

dynamic data structure

• Can grow and shrink in size

• Permits discarding of unwanted memory during execution time

• Linked list implementation of ADTs

array-based list-implementation

Inserting an element at the head of an array-based list requires shifting all existing elements in the array by one position toward the tail

structure in c++

• A collection of data items of different data types

• The data items are called members

• Defined using the struct keyword

• Creates a new user defined data type

dot operator

Used to access data members of structure variables

arrow operator

Used to access data members of pointer variables pointing to the structure

self-referential structures

Structures that can hold pointers to instances of themselves

linked-list based implementation

• Makes use of pointers

• Uses dynamic memory allocation

• Is a self-referential structure

• A collection of elements called nodes, each of which stores two types of fields

  • Data items (actual elements on the list)

  • Pointers to the next node (contains address of the next node in the list)

head

Special pointer that points to the first node of the linked list so that we can keep track of the linked list

NULL

The last node on a linked list should point to ____ to show that it is the last link in the chain

types of linked lists

• Singly

• Doubly

singly linked list

• Each node only has one link part

• Each link part contains the address of the next node in the list

• Link part of the last node contains NULL value which signifies the end of the node

basic operations on a list

• Creating a list

• Inserting an element in a list

• Deleting an element from a list

• Searching a list

insertion at the beginning

1. Make the next pointer of the node point towards the first node of the list

2. Make the start pointer point towards this new node

   1. If the list is empty, simply make the start pointer point towards the new node

insertion at the end

1. Declare a second pointer to step through the list until it finds the last new node

2. Make the next pointer of the last node point to the new node

displaying a list of nodes

1. Set a temporary pointer to point to the same thing as the start pointer

2. If the pointer points to NULL, display the message “End of list” and stop

3. Otherwise, display the details of the node pointed by the start node

4. Make the temporary pointer point to the same thing as the next pointer of the node it is currently indicating

5. Jump back to step 2

traversing forward through a list

1. Set a pointer to point to the same thing as the start pointer.

2. If the pointer points to NULL, display the message “list is empty" and stop.

3. Otherwise, move to the next node by making the pointer point to the same thing as the next pointer of the node it is currently indicating(using current pointer).

traversing backward through a singly-linked list

1. Set a pointer to p point to the same thing as the start pointer.

2. If the pointer p points to NULL, display the message “list is empty" and stop. Otherwise move forward until you find the last node.

3. Set an other new pointer q(which will later point to the node that is previous to p) and assign the same value as start pointer and move forward until you find the node before the one we are considering at the last node.

4. Set the p pointer equal to the other new pointer q (previous pointer)

5. Jump to step one

cases of deleting a node in SLL

• Deleting the first node

• Deleting the last node

• Deleting an intermediate node

deleting the first node

1. Set a temporary pointer temp pointing to the same thing as the start pointer

2. If the start pointer points to NULL display the message “List is Empty” and

3. Else make the start pointer point towards the 2nd node.

4. Deleting the temp node using delete keyword

deleting the last node

1. Set a temporary pointer q and temp

2. Move forward q and temp so that temp points to the last node and q points to the second last node(previous to temp)

3. Make the second last node’s next pointer point to NULL

4. Deleting the temp node via delete keyword

deleting a particular node

Here we make the next pointer of the node previous to the node being deleted, point to the successor node of the node to be deleted and then delete the node using delete keyword.

doubly linked list

• Each node points not only to Successor node (Next node), but also to Predecessor node (Previous node).

• There are two NULL: at the first and last nodes in the linked list

• It is not necessary to have start pointer, we can have any pointer(current) pointing to one of the node in the list

advantage of doubly linked list

• Given a node, it is easy to visit its predecessor (previous) node. It is convenient to traverse linked lists forwards and backwards.

• Some operations, such as deletion and inserting before a node, become easier.

disadvantage of DLL

• Requires more space.

• List manipulations are slower (because more links must be changed).

• Greater chance of having bugs (because more links must be manipulated).

necessity of start pointer in SLL

Having moved on from one node to another, we can’t easily move back, so without the start pointer, we would lose track of all the nodes in the list that we have already passed

optionality of start pointer in DLL

With the doubly linked list, we can move the current pointer backwards and forwards at will.

traversing backward through DDL

1. Set a pointer to point to the same thing as the current pointer

2. If the pointer points to NULL, display the message “list is empty" and stop

3. Otherwise, move back to the previous node by making the pointer point to the same thing as the previous pointer of the node it is currently indicating

deletion of node in DDL

• Involves changing two links for deletion

• Cases involving first/last node are special cases

application of linked-list

• Applications that have an MRU (Most Recently Used) list (a linked list of file names).

• The cache in your browser that allows you to hit the BACK button (a linked list of URLs).

• Undo functionality in Photoshop or Word (a linked list of state).

• A stack, hash table, and binary tree can be implemented using a doubly linked list.

circular linked list

• The last node points to the first node of the list

• Can finish traversing the list by checking if the pointer of the current node is equal to the start/head pointer