List as an abstract data type

A list is nothing but a collection of objects of the same type.

• stores n elements of type T
• Write or modify any element at position p
• Read any element at position p

We can expand on this by adding features and making this more generic

• empty if list has size 0
• insert at any position p
• remove from any position
• count items
• read/modify at any position
• specify data type

Any time we need to reallocate a new array, we should double the size

Linked List

C Implementation

struct Node {
struct Node* nextNode;
int data;
};

void addNode(int data){
node* cur = head;
if(cur == NULL){
	
}

}

int main(){

Node* head = NULL;



}

(Node*)malloc(sizeof(Node));
(*cur).data = data; //can also write cur->data=data;
(*.nextNode)= NULL;// can also write cur->nextNode;
head = cur;

CPP implementation

Node* temp = new Node();

Inserting a node at the end of a linked list

Node* cur = head;
Node* temp = new Node();
temp->data = 4;
temp->nextNode = NULL;

while(cur->nextNode != NULL){
	cur->cur->nextNode;
}
cur->nextNode = temp;

Inserting at the Head of a List

Node* temp = (Node*) malloc(sizeof(Node));
temp->data = 4;
temp->nextNode = head;

head = temp;

Print

void printList(Node* head);
Node* cur = head;
while(cur != NULL){
	printf(data\n);
	cur = cur->next;
	
}