Linked list data structure

January 4, 2018

Introduction

It is best time for me to work on the algorithm and give my own understanding to the peer. Here is one of algorithms I like to look into more.

First let me document the discussion first.

Problem statement: Given two vectors which are sparse, calculate the sum of product of two array, and create a data structure.
For example, first vector [1, 0, 0, 0, 1], and second vector is [2, 0, 1, 0, 0],
and then calculate the sum of 1 * 2 + 0 * 0 + 0 * 1 + 0 * 0 + 1 * 0.

Analysis:

I like to use the single linked list to reprent the vector, each vector two single linked lists are used, one for the index value,
one for the value of itself.

For example, vector [1, 0, 0, 0, 1] can be represented by index linked list:
 0 -> 4, array length = 5

index value ->       0 -> 4
value linked list -> 1 -> 1

-> up

[2, 0, 1, 0, 0] -> 0 -> 2 , length - 5 -> million
-> down

up -> 0 1 * 2 = 2 -> sum
up -> sum + 0 = sum

Problem -> optimal structure -> merge two lists ->
0 -> 2 -> 4

[1 * 2 + 0 * 0 + 0 * 1 + 0 *0 + 1 * 0]