Linked Lists

Data structures Series  – Blog 02


Linked Lists

Welcome back! Let’s continue with the data structures theme. Here’s the blog on the next data structure – that would solve the problem we had with arrays. Essentially, these two problems :

a. Arrays had fixed size , that needed to be specified when we define them. Resizing is an issue. So, developer might allocate a worst case array size, that may not be efficient if the number of elements to be held varies.

b. When we want to rearrange data in an array or insert data in between or front of an array, it  gets expensive.

Linked lists are the data structures which will help us in addressing these issues. Arrays and linked lists both essentially provide a way to store data for a client. Although linked lists to be discussed today, are good for cases arrays may not be great, they do come with their own limitations. We will cover it all in this blog, keep on reading.


Basic Stuff

If you have ever wondered why people often quiz you about linked lists? Wonder no more. It’s  because these are the most basic data structures that form the foundation for understanding more advanced data structures ( such as: binary trees, queues) etc.

Let’s suppose you need to write some basic C program to read all words (strings) contained in an input file. The first question that we would have is – How would you store the words read by the program? If we used a string array here, what would be the size to be allocated for the array? The number of words in the file is not known.

In this case, if we used a linked list, we can read words without wasting memory or be running out of memory (as would be the case, if we used arrays). This is because, as the name implies, linked lists are nothing but a list of elements linked together using a pointer parameter, in addition to the data that needs to be held – words in this case. So, the items to be inserted are just linked to the list, dynamically as and when required.

Now that we have a use case in mind, let’s learn about the internals of linked lists, operations supported and some overheads associated with their usage.


Internals

Linked list data structure are similar to arrays, but use an extra parameter – a pointer to link the items together. With this additional overhead of pointer per entry of data to be held, we can overcome the disadvantages of arrays and use memory efficiently. Linked lists use a different strategy for allocating memory for elements as compared to arrays. They allocate memory per element, when a new element needs to be inserted, not as a block as in case of arrays.

As shown below, a set of integer elements are organized in a linked list as shown on the right. We can note that there is an extra address field, that links the items together in the list. Values {2,3,5,7,8} are the data elements. We can clear;y see there is an overhead per element, to hold the pointer to next data element, in case of linked lists. But, even with this, we may be more memory efficient than arrays, when we perform operations such as always insert to the top of the list or storing elements in memory when the number of elements is not known apriori.

arr_ll
Fig 1. Arrays and linked lists elements in memory

We define a linked list element/node and a create a linked list, as below :

/* define node element for a Singly linked list*/
typedef struct Node{
int data;
Node* next;
}Node;

/* function to create and return linked list node */
Node* create_node(int data){
Node* n = (Node*) malloc(sizeof(Node));
n->data = data; // store the data
n->next = NULL; // initialize next address to NULL
return n;
}

/* Example code to create a linked list of nodes 
*  Creates a linked list with three data elements/nodes 
*  Linked list : n1->n2->n3->NULL */ 

Node* create_test_list(){

Node* n1 = create_node(10);
Node* n2 = create_node(20);
Node* n3 = create_node(30);

// update pointers
n1->next = n2; // n1 holds pointer to n2
n2->next = n3; //n2  holds pointer to n3

// n3 is the last node of this list and 
// next shall be stored as NULL to imply this.

}

Operations supported

We can implement various operations on linked lists such as insert(), delete(), lookup(), hasloop(), removeloop()  and so on. It would be a good idea to write code for these operations, to understand linked lists better. Check [1] and [2] under references below to get started.


Doubly Linked List

These are similar to singly linked lists discussed above. But, instead of holding pointer only to the next element, there is an additional pointer per node to point to the previous element as well. Why do we need them? Wait for next week’s blog 🙂 ll1.png

/* Singly Linked list node */
typedef struct Node{
int data;
Node* next;
} Node;

/* Doubly Linked list node */
typedef struct d_Node{
int data;
Node* next ; 
Node* previous; // extra pointer in doubly linked list
} d_Node;


Drawbacks

What do you think would be the drawback of a linked list, other than the storage of extra parameter – i.e., a pointer per element. Yes! It is the insert at the nth location and also lookup nth element operations. In arrays, we had an O(1) look up and also O(1) updates.

But, with linked lists, we have to iterate all the n-1 nodes, to find the place to insert nth node to the list. Also, if we want to look-up nth node, we need to traverse n-1 nodes, before we get the value of nth node- resulting in O(n) cost.

Visual is always better to understand. Please check the picture below.

ll1
Fig 2. Insert at nth position, operation on arrays and linked list

 


Further Reading

  1. Linked list problems (Stanford)
  2. Solve some problems related to linked lists

Next, we shall explore the Binary Search Tree data structure which is realized using a doubly linked list discussed here. As always, write to me at decodergirlblog@gmail.com if you have any queries or suggestions. I would love to hear from you. Until then, keep decoding and enjoying your coffee ! 😉

 

Did you know?

More coffee you donate, higher is your coder karma! Oh! there shall also be more blogs published here. Thank you for being awesome! 😀

$1.00

Life After School…

I. QWCC

Recently, I had the opportunity to be part of QWCC (Qualcomm Women Collegiate Conference) – a two day event, to serve as a mentor and also a Judge for an Hackathon. I have been wanting to write about my key take away from this event. And, finally here it is.   

QWCC’s goal is to help female freshman to senior students become more successful by providing them with pointers on development of technical and professional abilities , enabling them to build a network of peers while exposing them to industry. The event includes campus tours, lunch with the mentor , technical overviews , networking and development activities that included Hackathon.  The event had about 50 students selected from across the country. As a mentor, on day one , I had the opportunity to connect with two students – one freshman and the other a senior. This session had me answering queries they had right from engineering as a career choice to being an engineer at Qualcomm. I enjoyed the fact that the girls were uninhibited and seemed to go by the adage : No question is silly. They asked me about my project at Q, why I choose this over other projects and what’s the most interesting and challenging part in it . It seemed like they were interested in understanding what makes an engineer at Q tick at the core ! While answering their questions, it seemed to ring a bell as to what is that I have enjoyed being at work.

IMG_20170121_131245_456-mod.jpg

On day two, I was part of a unique hackathon event that had these girls divided into small groups and teamed up with young middle school girls, to come up with a prototype of an idea under one of the three areas : health care, public safety or wearables. They could use Arduino, different types of sensors to prototype the idea in about 3-4 hours. The point of this event  was to help the girls experience working in collaborative ensembles, develop leadership abilities and of course see how they utilize the technical learning and apply them to real world problems. It was pretty amazing to see these girls guide the middle school girls and involve them in the project and come up with “working” prototypes of ideas all within the allotted time. The room (pic above) was beaming with curiosity, enthusiasm and willingness to learn and explore. Many had not even worked on this platform before, they learnt it on the spot to prototype their idea. As the girls presented their prototypes and I continued with judging the event, I had begun to think about what happens to learning once we are out of school.

II. Never Stop Learning

I have always believed learning doesn’t and shouldn’t stop when we step out of school. It’s a continuous process. Isn’t the spirit of learning, exploring something that makes everyday interesting. Of course, the rewards and other desires are part of this journey, but isn’t enjoying the process the core of it? There have been innumerable articles online about how learning new things benefits our brain (ex : outlined here , based on nature journal article) and also helps as we age (npr article). There are also articles such as “how-developers-stop-learning: rise-of-the-expert-beginner” that highlight what happens particularly as a developer, when we begin work and stagnate after a certain point.  This article is an interesting read and depicts a modified Dreyfus model of skill acquisition  to show that when developer discontinues learning, he essentially ends up being an ‘expert beginner‘.

In addition, I found this article by Matthew D. Lieberman from UCLA about “Why we stop learning – paradox of Expertise. He talks about why learning ceases once people begin working and most importantly why it should not. He particularly points out that as one rises up in career, it  becomes harder for the person to let others know that he/she doesn’t know everything – that others think they know and hence becoming increasing essential that they let themselves out of this self-presentational vice. He further talks about how to deal with this and learn new things without feeling sheepish about it.  Please do give his article a read. Most importantly, as he says : “Take the time now to remind folks, including yourself, that no matter how much expertise you have, you will continue to be a learner.  If you do that, there’s a pretty good chance you will”. So, here’s hoping this blog entry serves as a gentle reminder and/ motivation to keep learning.

When we enjoy the process of learning and collaborating, working successfully in groups and achieving what you set out to, is consequential

“Live as if you were to die tomorrow. Learn as if you were to live forever.” – Mahatma Gandhi.

Demystifying Grace Hopper Celebration

People often ask me why is there a conference only for women; isn’t the day we have no such conference – the time we have truly achieved equality? I do agree with this thought. But, to me this conference is not a celebration “for minority” but a celebration of the fact, as to how far we have come from being termed the minority.

Grace Hopper Celebration is the world’s largest conference for women in computing that has grown from a mere 500 women who came together in 1994 to 15,000 plus participants this year. This truly highlights the progress we are making on closing the gap between men and women in the field of Computing. It is needless to say how motivating and inspiring it was to learn about some wonderful women in the field and the contributions they have been making.

I had the opportunity to represent Qualcomm and be part of this amazing conference for the second time. I was introduced to this conference by fellow engineer Molly Nicholas, with whom I had collaborated on the idea of designing a hardware called Qbadge in the year 2015 – added wireless connectivity to the Hardware – (what I do best, of course ! ;)) and also some new neo-pixel patterns to light up the badge (check video below).  This was one of the few times, I had designed something on a basic breadboard and tested (pic below). It’s awesome what you explore and do when you collaborate.

Qualcomm hosted a Hackathon event that utilized the Qbadge hardware again in 2016. I was excited to be part of this event, to meet and answer the questions from the participants – young women engineers chosen from across the United States. The idea was to have a useful social interaction, make it a learning experience for the girls by exposing them to low level programming. We had them edit the programs loaded on the badges, while they solved some hackathon clues.

screenshot_2015-07-13-17-32-29-2    screenshot_20170304-125705

Pic 1 : Arduino Trinket interfaced with Bluetooth HC -05 chip

Pic 2: Internals of QBadge

Video below : Shows how the badge flashes with the programmed neopixel patterns that can be activated by a command from an Android app sent over Bluetooth connection:

One of the feedback I had from the first time at the conference in 2015 was that more men should also participate in this conference. Q showed an increased participation from the previous year , from 50 participants to 130 that included a few men as well. At the booth, Qualcomm had an invisible museum- named invisible but truly impactful Augmented Reality display. This seemed in-line with Megan Smith’s opinion she shared with a quote during her key note : “Women have always been an equal part of the past. We just haven’t been a part of history” – Gloria Steinem. This is very much the premise for Grace Hopper Conference – to recognize and highlight the contributions that women are making as well.

In my opinion, it would be a  good idea for more men to be a part of this conference to not only learn about and appreciate the contributions made by women but also to gain awareness about how they could aid with the efforts to close the gender gap, by getting involved in discussions about the problems or challenges faced by women. There were a number of men who were not only present at the conference but also made presentations such as this talk by Astro Teller, Google X.

Moving on, the technical theme for the year 2016 included Internet of Things, Artificial Intelligence, Human Computer Interaction and Data Security. While various technical talks in all the above tracks, such as self driving cars, programming humanoids, connecting millions of devices – engaged me and were giving a glimpse of tomorrow, there were also talks about solving the connectivity problem that had my attention. With the world progressing towards Drones, Smart Vehicles and Devices, Internet of Things – an all connected paradigm, it’s hard to imagine that two thirds of the world still remains unconnected – has no access to basic internet. As an Engineer at Qualcomm Research, I am excited to be part of the team that is working on connecting the unconnected.

Working on a myriad of problems and finding solutions for the questions of today and tomorrow, is what makes engineering a challenging as well as an enjoyable task. The term engineer has no gender. I believe that building a future we envision, takes each one of us and the path to that is – coming together and looking beyond the gender!

Lastly, to give you a sneak peak of how women are getting ahead on closing the gender gap in the tech industry, the winner of ABIE award for Technical Leadership,2016: Anna Patterson tried a simple way using the “show of lights” from the mobile phone to represent the show of strength. (video below)

But, it was her words : “No matter what you are going through, there is always a lesson to be learned and light at the end of the tunnel. Make sure you are looking for the light”  – that resonated  with me as I witnessed the entire hall light up around me!

More importantly, this made me realize how each one of us can make a difference to the over all picture. This post is dedicated to all the women engineers out there. Thank you to each of you for doing your bit and inspiring me each day to keep going. Together – we got this ! 


Note : This post in response to the Day-04 prompt word : “inspiration” – created by thestemsquad on Instagram in the on-going month of ‘get to know women in STEM’ initiative.