Posts Tagged ‘list’

A Tour On Python List

Posted: May 28, 2015 in Programming
Tags: , , ,

 For those who have used Arrays in C and C++, list in Python is going to be a lucky charm . As Head First Python states, List is nothing but an array with steroids. Python list makes the life very easier as its dynamic in nature and the in-build functions are available to perform all the actions on it.

First lets list down the basic stuffs that we always do on arrays .

1. Declaring
2. Creating
3. Initializing with predefined input
4. Adding More input to it
5. Searching
6. Indexing
7. Removing
8. Erasing
9. In Built Functions

In this tutorial, am going to use 2 lists. One named numbers and other named alphabets. Lets go and see one by one .

1. Declaring a list

As we know, we need not declare a variable with appropriate data type in python . both a = 5 and a = ‘5’ are valid without specifying the corresponding data type. And more importantly, its applicable to lists as well.

2. Creating a list

When i say creating , it has 2 modes. Creating an empty one to add items later. Or creating a predefined set of elements in the list. To create an empty list, all we need to do is to write an open and closed square brackets.

numbers = []

https://shrinathsuccess.files.wordpress.com/2015/05/list2.png?w=614

3. Initializing with Predefined Input:

Sometimes, we will be really sure that we are going to work with only some specific inputs. In those situations we can create a list with pre defined inputs in it. That can be done by enclosing the inputs inside the square bracket

numbers = [1,2,3,4]

https://shrinathsuccess.files.wordpress.com/2015/05/list3.png?w=614

4. Adding more input to a List:

Adding input to the list can be categorized as following

4.1 – Adding elements one by one to a list
4.2 – Adding elements in a block
4.3 – Multiplying the list
4.4 – Adding list inside a list

4.1 – Adding elements one by one to the list :

Python has predefined function named “insert” , which can be used to add elements to the list. However, the insert takes two arguments. first one is the position and second one is the value. The list with numbers 1,2,3,4 can also be created as below

numbers = []
numbers.insert(0,1)
numbers.insert(1,2)
numbers.insert(2,3)
numbers.insert(3,4)

https://shrinathsuccess.files.wordpress.com/2015/05/list4-1.png?w=614

4.2 – Adding elements in block

If suppose we have 2 lists. first one containing numbers 1 to 3 and other one containing numbers 4 to 6. And we need to merge two list. ie. adding elements in block, then we can do it as below:

num1 = [1,2,3]
num2 = [4,5,6]
num1 + num2

or simply

[1,2,3] + [4,5,6]

https://shrinathsuccess.files.wordpress.com/2015/05/list4-2.png?w=614

4.3 – Multiplying the list

Python creates a easy way of inserting repeated items. For example, if we need a list which has 3 numbers 1,2,3 ten times. we need not write a for loop . Just a simple multiplication operator on list will do it as below

numbers = [1,2,3]
numbers * 10

https://shrinathsuccess.files.wordpress.com/2015/05/list4-3.png?w=614

4.4. Nesting Lists

Yes, we can have list inside a list. And there is a specific way for indexing the list. In the list below , 4th item is a list which contains 3 items in turn.

numAlpha = [1,2,3 [ “a”, “b”, “c” ]]

https://shrinathsuccess.files.wordpress.com/2015/05/list4-4.png?w=614

5. Searching an element in the list

If we need to check an element exists in the list , we can use “in” keyword with list which will return a boolean value (True indicating the element exists and false indicating the element doesnt exist in the list)

numbers = [1,2,3,4,5,6]
4 in numbers
7 in numbers

https://shrinathsuccess.files.wordpress.com/2015/05/list5.png?w=614

6. Indexing list

We can get the element based on the index of that element in the list. Since, all the elements are inserted into the list with the index element, we can derive any element if we know the index. Index starts with 0 and moves on as we insert the elements.

List_name[start : end]

This is the common notation . start denotes the starting index that we need to start with, to start from beginning give 0 or leave it empty. End denotes the position to which list should print

numbers = [1,2,3,4,5,6]
numbers[1:4] - show elements from index 1 till 3
numbers[:2] - show elements from beginning till 1st index
numbers[2:] - show elements from index 2 to end of the list
numbers[:] - print all elements
numbers[-2] - tricky one .. show 2nd last element in the list

https://shrinathsuccess.files.wordpress.com/2015/05/list6.png?w=614

7. Removing elements from a list :

We can remove an element from the list if we know the index or element value. remove function can be used if we know the list value and del function can be used to remove using index.

numbers = [1,2,3,4,5,6]
numbers.remove(5)
numbers
del numbers[-4]
numbers

https://shrinathsuccess.files.wordpress.com/2015/05/list7.png?w=614

8. Erasing the list :

If we need to erase all the elements in the list , we can use clear function . List_name.clear() will remove all the elements from list.

numbers = [1,2,3,4,5,6]
numbers.clear()
numbers

https://shrinathsuccess.files.wordpress.com/2015/05/list8.png?w=614

9. Inbuilt Functions :

There are lot of inbuilt functions available in python list. One that we saw is len(list_name) which gives the length . Similarly we have

len – finds the total number of elements in the list
count – finds the number of occurrence for an element
sort – sorts the list
reverse – reverse the list
index – returns the index of first matching element

https://shrinathsuccess.files.wordpress.com/2015/05/list9.png?w=614

Advertisements

WHAT IS LINKED LIST :

Linked list is a data structure which contains a set of elements linked to its successor.

WHERE TO USE LINKED LIST :

When there is a need of lot of insertions and deletions , linked list is preferred over Array .

One simple example is this : Say we have array of 1000 numbers . 2 to 1001 . Now we need to insert 1 at the beginning of the array. Its not so simple, we need to shift all the numbers from 2 to 1001 one step right for inserting one element at the beginning.

Linked list over comes this problem. Just allocate memory and play with pointers to give connections. 1 will be inserted at the beginning.

WHERE NOT TO USE LINKED LIST :

There are certain scenarios where in we need more number of searches than insert and delete. On such occasion arrray gives us a better result.

HOW TO IMPLEMENT LINKED LIST :

In this post we will be discussing 12 basic set of items on linked list

1. Structure of Linked List

2. Creating One node Linked List

3. Creating 3 Node Linked List

4. Creating N Node linked List

5. Inserting a node at front of linked list

6. Inserting a node at end of linked list

7. Inserting a node at N point of linked list

8. Deleting first element from list

9. Deleting last element from list

10. Deleting random element from list

11. Searching linked list

12. Copying Linked list

STRUCTURE OF LINKED LIST

                       Structure Of Linked List

A linked list contains data element along with the pointer which points to the next element.

struct node
{
     int data;
     struct node* next;
};

Creating One node Linked List:

                                         Single Node Linked List

Lets create a simple one node linked list . For creating a node , we need to follow three steps.

  1. Create a new node pointer
  2. Allocate memory and insert element
  3. Point the pointer to appropriate position
#include  // for cout
#include  // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);

int main()
{
        // create head pointer
        struct node* head = NULL;

        // allocate memory to it
        head = (struct node*) malloc(sizeof(struct node));

        // insert the data
        head->data = 1;

        // point the next pointer
        head->next = NULL;

        // printing the list
        print_ll(head);
        return 0;
}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

Output of single node linked list

CREATING 3 NODE LINKED LIST

                                    three_node_ll

Now, we know the size of linked list. So, lets create a function that will build 3 nodes in a linked list.

#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
struct node* three_node_ll();

int main()
{
        // call the function to create the list
        struct node* head = three_node_ll();
        // printing the list
        print_ll(head);
        return 0;
}

struct node* three_node_ll()
{
        // create 3 pointers for 3 nodes
        struct node* head = NULL;
        struct node* second = NULL;
        struct node* third = NULL;

        // allocate memory for 3 nodes
        head = (struct node*) malloc(sizeof(struct node));
        second = (struct node*) malloc(sizeof(struct node));
        third = (struct node*) malloc(sizeof(struct node));

        // insert data into 3 nodes and point the sequence in right order
        head->data = 1;
        head->next = second;

        second->data = 2;
        second->next = third;

        third->data = 3;
        third->next = NULL;

        return head;

}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

three_node_output

CREATING N NODE LINKED LIST

In the previous case, we know the definite size of linked list . But , now we need to build a list based on the input given by the user. Hence , we need to write a generic function which will insert the numbers into list dynamically.It is easy to push elements at the front of the list . It comprises of 3 steps.

  1. Allocate memory for the new node and insert data into it.
  2. Point the next pointer to old head
  3. Change head to new node
#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
void n_node_ll(struct node*&,int);
int num_of_nodes;

int main()
{
        cout << "Enter number of nodes to be created " << endl;
        cin >> num_of_nodes;
        struct node* head = NULL;
        // call the function to create the list
        for(int i=0 ; i<num_of_nodes; i++)
        {
                n_node_ll(head,i+1);
        }
        // printing the list
        print_ll(head);
        return 0;
}

void n_node_ll(struct node*& head, int d)
{
        // allocate memory and insert data
        struct node* newNode = (struct node*) malloc(sizeof(struct node));
        newNode->data = d;
        // point next pointer to old head
        newNode->next = head;
        // point head to new node
        head = newNode;
}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

INSERTING NODE AT FRONT OF LINKED LIST

n_node_ll

Say, we have linked list with 2 elements . 4 and 3 . Now we need to push 5 into the list at the front .

As explained in the previous code , it will be done with same 3 steps.

#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
struct node* two_node_ll();
void insert_at_front(struct node*&,int);

int main()
{
        // call the function to create the list
        struct node* head = two_node_ll();
        // inserting number 5 at the front
        insert_at_front(head,5);
        // printing the list
        print_ll(head);
        return 0;
}

void insert_at_front(struct node*& head,int d)
{
        struct node* current = head;

        // create node and allocate memory
        struct node* newNode = (struct node*)malloc(sizeof(struct node));

        //insert data into the memory
        newNode->data = d;

        // point the next pointer to old head
        newNode->next = head;

        // change head of the list to new node
        head = newNode;
}

struct node* two_node_ll()
{
        // create 3 pointers for 3 nodes
        struct node* head = NULL;
        struct node* second = NULL;

        // allocate memory for 3 nodes
        head = (struct node*) malloc(sizeof(struct node));
        second = (struct node*) malloc(sizeof(struct node));

        // insert data into 3 nodes and point the sequence in right order
        head->data = 4;
        head->next = second;

        second->data = 3;
        second->next = NULL;

        return head;

}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

insert_at_front

INSERTING A NODE AT END OF THE LIST

insert_at_end

For adding the node at the tail end we need to follow these steps

  1. Iterate through the list and find the point the last element in the list
  2. Create new node and insert data to it
  3. Point the next pointer of new node to null since it is going to be the last element
  4. Link the old last element pointer to new node
#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
struct node* two_node_ll();
void insert_at_end(struct node*&,int);

int main()
{
        // call the function to create the list
        struct node* head = two_node_ll();

        // inserting number 3 at the end
        insert_at_end(head,3);

        // printing the list
        print_ll(head);
        return 0;
}
void insert_at_end(struct node*& head,int d)
{
        struct node* current = head;
        while(current->next != NULL)
        {
                current = current->next;
        }

        // create node and allocate memory
        struct node* newNode = (struct node*)malloc(sizeof(struct node));

        //insert data into the memory
        newNode->data = d;

        // point the next pointer to null since its the last element
        newNode->next = NULL;

        // change head of the list to new node
        current->next = newNode;
}

struct node* two_node_ll()
{
        // create 3 pointers for 3 nodes
        struct node* head = NULL;
        struct node* second = NULL;

        // allocate memory for 3 nodes
        head = (struct node*) malloc(sizeof(struct node));
        second = (struct node*) malloc(sizeof(struct node));

        // insert data into 3 nodes and point the sequence in right order
        head->data = 5;
        head->next = second;

        second->data = 4;
        second->next = NULL;

        return head;

}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

output_insert_at_end

 

 

 

 

In my previous post i have written a program which prints all permutations of a word.. But i end up with a problem..

consider the input is abc.. Output will be

abc
acb
bac
bca
cab
cba

yeah.. it’s fine.. but now input is aba

aba
aab
baa
aab
aba

we can see the repetition of words.. To avoid that i have used a list which stores all the words and prints only the unique possibilities.

 

#include “iostream”
#include “string”
#include “list”

using namespace std;

void permute(string,int,int);
void store_to_list(string);
void swap(string&,int,int);
void rotate_left(string&,int,int);
string word;
list mylist;
list::iterator it;
int main()
{
cout<>word;
int len=word.length();
permute(word,0,len);
cout<<“\n\n”;
mylist.sort();
mylist.unique();
for( it = mylist.begin() ; it != mylist.end() ; it++ )
{
cout<<*it<<endl;
}
cin.get();
cin.get();
return 0;
}

void permute(string w, int start, int n)
{
store_to_list(w);
if(start=start;i–)
{
for(j=i+1;j<n;j++)
{
swap(w,i,j);
permute(w,i+1,n);
}

rotate_left(w,i,n);

}
}

}

void store_to_list(string w)
{
mylist.push_back(w);
}

void swap(string &w,int i,int j)
{
char t;
t=w[i];
w[i]=w[j];
w[j]=t;
}

void rotate_left(string &w,int go,int n)
{
char tmp=w[go];
for(int i=go;i<n-1;i++)
{
w[i]=w[i+1];
}
w[n-1]=tmp;

}

 

Now for the same input aba output will be

aab
aba
baa