DSList

New Data Structure created by linux term project

Comparison of Structure

1. Linked list

• Total memory usage = 2 * (4byte + 4byte + sizeof(data)) = 16byte + 2*sizeof(data)

2. DSList (Double Storage List)

• Total memory usage = 4byte + 4byte + 1byte + 2sizeof(data) = 9byte * 2sizeof(data)

*** Existing Doubly Linked List (picture 1) uses 8bytes for each node ***
*** We devised new data structure that improves preformance in respect of memory usage ***
*** We store twice more data in one node and call this "cluster" ***

DSList Data Structure

• Inserted two data in one node and linked clusters. We call this "Double Storage List", DSList
• Components
  -> list_head : same with existing linux's doubly linked list
  -> toggle : flag variable that indicates structure up / down has data
  -> structure up & down : data stored in each position
  
• Advance in Memory Storage
  -> save 7bytes for each cluster by changing data structure of single node