Singly Linked Lists

 _____________________________________________________________________________________________________________

Wolmer’s Trust High School for Girls

CAPE COMPUTER SCIENCE – UNIT 2

 

Grades:  Upper                                                                               Teacher:  Mrs. McCallum-Rodney

 

 

INTRODUCTION

WATCH THESE VIDEO BEFORE YOU START READING -  

                   http://www.youtube.com/watch?v=LOHBGyK3Hbs

              http://www.csanimated.com/animation.php?t=Linked_list

 

DEFINITION

Þ    A list that displays the relationship of adjacency between elements is said to be linear list. It also can be defined to consist of an ordered set of elements.

Þ    Array sizes have to be declared at compile time, before the program executes.  List implementation can avoid these problems if the list can grow and shrink dynamically, as the program is executing.  The type of list that does that is called a linked list.

Þ    Linear linked list is the most commonly used data structure of linked lists.

 

STRUCTURE OF LINEAR LINKED

Þ    Consider the following concept:

If you have a to-do list, you are not quite sure how many thinks you have to do.  Instead of having a single sheet of paper, we have several strips of paper, each big enough to hold one item.  The strips of paper have fasteners to allow them to connect to each other.  Then, you can use the exact amount of paper you need for the list you are maintaining.  If you need to remove an item, you just need to remove the strip of paper with the item on it. 

This is the basic concept of a linked list implementation.

Þ    In linked lists a node is equivalent to our strip of paper.  It holds the element that is being stored in the list.  It also has a pointer (a fastener) to the next node in the list.  Note:  A pointer is a memory location that holds the address of another memory location.

Þ    A simple way to represent a linear list is to expand each node to contain a link or pointer to the next node. (see Figure below).

 

In the figure above, the variable Head contains an address or pointer that gives the location of the first node of the list. The last node of the list does not have a successor node, and consequently, no actual address is stored in the pointer field. In such case, a null value is stored as the address. The arrow coming from the link field of a particular node indicates its successor node in the structure.

OPERATIONS OF LINEAR LINKED LISTS

Þ    The basic operations of linear linked list include insert, delete, and search.

1. OPERATION - INSERT

Insertion is to add a new node into a linked list. It can take place anywhere -- the first, last, or interior of the linked list. We will only discuss insertfirst and insertlast. To perform the insertion, we need a temporary pointer, new, that points to a node that will be added into the list.

 

 

Insert First

 

Þ    This will insert a new element as the first element of the link list.

Þ    To add a new node to the head of the linear linked list, we need to construct a new node that is pointed by pointer new. Assume there is a global variable head which points to the first node in the list. The new node points to the first node in the list. The head is then set to point to the new node.

 

 

 

                    

The following figures show the procedure step by step.

Step 1. Create a new node that is pointed by pointer new.

Step2. Link the new node to the first node of the linked list.

Step3. Set the pointer head to the new node.  

 

Insert Last

 

Þ    Insert element at the end of the link list.

Þ    To add a new node to the tail of the linear linked list, we need to construct a new node and set it's link field to "null". Assume the list is not empty, locate the last node and change it's link field to point to the new node.

 

 

 

 

The following figures show the procedure step by step.

Step1. Create the new node. Initializing pointer cur points to the first node of the list, while the pointer prev has a value of null.

Step2. Traverse the entire list until pointers prev and cur advanced to the end of list. To advance cur and prev one node forward, we first advance the pointer, prev, and then move cur.

Step 3. Assign the value of the LINK part of new node to null.

Step4. Link the node that is pointed by pointer prev to the new node.

 

 

 

2. OPERATION - DELETION

 

Deletion is a common operation of linear linked list. It can remove the first node, the last node, or a node containing particular value in the linked list.

 

                     

Delete First

 

 

 

 

 

 

 

The following figures show the procedure step by step.

Step1. Initializing the pointer cur point to the first node of the list.

Step2. Moving the pointer head to the second node of the list.

head

 

Step3. Remove the node that is pointed by the pointer cur.

 

 

Delete Last

 

Þ    Delete last element of the link list.

Þ    To delete the last node in a linked list, we use a local variable, cur, to point to the last node. We also use another variable, prev, to point to the last second node in the linked list.

 

The following figures show the procedure step by step.

Step1. Initializing pointer cur point to the first node of the list, while the pointer prev has a value of null.

Step 2.Traversing the entire list until the pointer cur points to the last node of the list.

Step 3. Assign the LINK field of the node that is pointed by pointer prev to nil.

Step 4. Remove the last node that is pointed by pointer cur.

 

Delete within the list

 

Þ    Delete one of the element of the link.

Þ    To delete a node that contains a particular value x in a linked list, we use a local variable, cur, to point to this node, and another variable, prev, to hold the previous node.

 

 

 

 

The following figures show the procedure step by step.

Step1. Initializing pointer cur points to the first node of the list, while the pointer prev has a value of null.

Step2. Traversing the entire list until the pointer cur points to the node that contains value of x, and prev points to the previous node.

 

Step3. Link the node pointed by pointer prev to the node after the cur’s node.

 Step4. Remove the node pointed by cur.

 

 

3. OPERATION – SEARCH

 

Þ    Search the element of the link list.

Þ    As long as the linked list is not empty, we can search the list for the node containing particular value e. To accomplish this operation, we need two pointers, prev and cur. After completing the searching, the pointer cur will point to the node containing the value e, and prev will hold the previous node of cur’.

 

The following figures show the procedure step by step.

Step1. Initializing pointer cur points to the first node of the list, while the pointer prev has a value of null.

Step 2. Set prev point to the node pointed by cur.

 Step 3. Set cur point to the node after prev’.

 

Step 4. Repeat step2, step 3, until cur is pointing to the node that contains value e.                                          

 

 

CLASSWORK 

Ensure that your diagrams is carefully labelled.

1. Draw a node and label it propery.
2. Create an empty list.
3. Show a list with the values -   2, 3, 4 and 5. 
4. INSERT at the beginning of the list, the value 1.  Write the steps needed to do this.
5. INSERT at the end of the list, the value 6. Write the steps needed to do this.
6. DELETE the value 4.
7. SEARCH for the value 3.