Lecture 223:- Student Challenge Sparse Matrix using Linked List

 

Creating a sparse matrix using a linked list is an efficient way to represent matrices that have a large number of zero elements. In this representation, only the non-zero elements are stored, which saves memory and allows faster access to elements. Here's a basic implementation of a sparse matrix using a linked list in Python:

Let's start by defining the data structures for the sparse matrix:

pythonCopy code

class Node:    def __init__(self, row, col, value):        self.row = row        self.col = col        self.value = value        self.next_row = None        self.next_col = None class SparseMatrix:    def __init__(self, rows, cols):        self.rows = rows        self.cols = cols        self.row_heads = [None] * rows        self.col_heads = [None] * cols

Next, we can add methods to insert elements into the sparse matrix:

pythonCopy code

class SparseMatrix:    # ... (previous code)    def insert(self, row, col, value):        if row < 0 or row >= self.rows or col < 0 or col >= self.cols:            raise IndexError("Index out of range")        new_node = Node(row, col, value)        if not self.row_heads[row]:            self.row_heads[row] = new_node        else:            current_row_node = self.row_heads[row]            while current_row_node.next_row:                current_row_node = current_row_node.next_row            current_row_node.next_row = new_node        if not self.col_heads[col]:            self.col_heads[col] = new_node        else:            current_col_node = self.col_heads[col]            while current_col_node.next_col:                current_col_node = current_col_node.next_col            current_col_node.next_col = new_node    def get(self, row, col):        if row < 0 or row >= self.rows or col < 0 or col >= self.cols:            raise IndexError("Index out of range")        current_node = self.row_heads[row]        while current_node:            if current_node.col == col:                return current_node.value            current_node = current_node.next_row        return 0  # Return 0 for elements that are not explicitly set (i.e., zero)

With these basic methods, you can create and use a sparse matrix using a linked list. Here's an example of how you can use it:

pythonCopy code

# Create a 4x4 sparse matrix matrix = SparseMatrix(4, 4) # Insert some non-zero elements matrix.insert(0, 1, 5) matrix.insert(1, 0, 3) matrix.insert(2, 2, 7) matrix.insert(3, 3, 2) # Get elements from the sparse matrix print(matrix.get(0, 1))  # Output: 5 print(matrix.get(1, 0))  # Output: 3 print(matrix.get(2, 2))  # Output: 7 print(matrix.get(3, 3))  # Output: 2 print(matrix.get(1, 1))  # Output: 0 (implicitly a zero element)

Remember that the implementation can be further optimized and extended depending on your use case. This is a simple starting point to demonstrate the basic concept of a sparse matrix using a linked list.