About Us

Students have an amazing amount of value to offer one another, but most of that goes unrealized.

Our mission is to personalize higher education by allowing students to teach one another, in every format possible. Read our story in the main site menu.

 

    Linked Lists

    Intro

    A very important data structure, that is often confusing to beginning CS students, is the linked list. Linked lists are a linear data structure, just like basic arrays. However, unlike an array, the linked list is not one large, continuous block in memory. Instead, each element in a linked list contains a pointer to the next element. Each element is “linked” to the next, hence the term “linked list.”

    Linked Lists vs Arrays

    This might seem confusing at first, but let’s start by contrasting a linked list with an array. In an array, each element is accessible by an index. In Image 1, we can see this clearly. If we want the value of element 3, we just call num[2]. This is because the elements are all stored contiguously in memory, so we can move down the array to find the element we want.

    Image 1


    In a linked list, the elements are not contiguous. Rather, each element contains a pointer to the next element. Take a look at Image 2. If we want the value at B, we can’t just call num[1]. Instead, we follow the pointer head to get to A. Then, we follow the pointer of A to get to B, and there is our value.

    Image 2


    Linked List Implementation


    Why Linked Lists?

    Although more complicated, the linked list is a very useful data structure. With a linked list, there is no cost to resizing. As such, we can append, insert, or delete elements in constant time. With an array, this same operation takes linear time. With large data sets, this is a huge difference.

    Book a Tutoring Session

    Nikhil Razdan

    March 28, 2020

    View Profile

    Book a Tutoring Session