Linked list, some operations.

Linked List

With structures, a dynamic data structure is created with arbitrary number of nodes. Some of the operations that can be performed on a linked list is list below, followed by code
1.Create a linked list
2.Traverse a linked list
Print in increasing order
Reverse print
3.Delete a linked list node
Head node
Last node
Node with specific data
4.Insert a linked list node
At head
As last node
After a node with specific data

Part 1:

1.Create a linked list

A singly linked list node is created with a structure, with a data element and a link to the next element, which is of the same structure type, a self referential structure.

Here, a linked list of 10 node is created, with data element set as the increment. Algorithm to create a linked list is:

Have two pointers of the node type(Node *head,*current)

Create a new node,with ‘malloc’, providing the size of the structure node ‘Node’, then type casting it to ‘Node*’ pointer type, as ‘malloc’ returns a void*.

Set node’s next pointer to head and set the current node as the head. First step, set the last node’s next pointer to null and then head is set to the current node, so when the send node is created, head is not null, as the list is not null and head points to a single node, previously created.

Once the list is created with all the nodes, set head as the first node.

//1.Create a linked list
//
//  main.m
//  LinkedList
//
//  Created by Keynes Paul on 5/27/16.
//  Copyright © 2016 com.codeinobjc. All rights reserved.
//
#import <Foundation/Foundation.h>

@interface LinkedList : NSObject
-(id)init;
@end

@interface LinkedList()
typedef struct Node Node;
struct Node
{
    int data;
    Node *next;
};
@property(nonatomic,assign) Node *head,*current;
@end

@implementation LinkedList
-(id)init
{
    if (self == [super init]) {
//        initialize linked list with 10 nodes
        for (int i=0; i<=10;++i) {
            self.current = (Node*)malloc(sizeof(Node));
//set node data
            self.current->data = i;
//set next node as head, which is null now, altered in the next line as the current node
            self.current->next = self.head;
//set the newly created node as head, second node's next will point to this
            self.head = self.current;
        }
//set first node as head
        self.current = self.head;
    }
    return self;
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
// initialize a new linked list with 10 nodes
        LinkedList *list  = [LinkedList new];        
    }
    return 0;
}

2.Traverse a linked list

Traversing a linked list with the given head is a bad idea, so a temporary pointer is used to point to head and it is used to traverse the list.

Print in increasing order

Recursively traversing a linked list is easy, more on that in this post. Lets see the code here.

// Print a linked list in increasing order
-(void)printList:(Node*)head
{
//Have a temporary pointer
    Node *t = head;
//trivial condition; until node' next is not NULL
    if (t->next != NULL) {
//operation: print node' data element
        NSLog(@"%d",t->data);
//tail recursion
        [self printList:t->next];
    }
}
Reverse print
// Print a linked list in reverse order
-(void)printList:(Node*)head
{
//Have a temporary pointer
    Node *t = head;
//trivial condition; until node' next is not NULL
    if (t->next != NULL) {
//head recursion
        [self printList:t->next];
//operation: print node' data element
        NSLog(@"%d",t->data);
    }
}

3.Delete a linked list node

Given a pointer to a head node, any node on the linked list can be deleted. Common operations are;
Delete a head node
-(void)deleteNode:(Node*)head
{
    Node *temporaryPointerToHeadNode = head;
    head = head->next;
    free(temporaryPointerToHeadNode);
}
Delete last node
-(void)deleteNode:(Node*)head
{
    Node *temporaryPointerToHeadNode = head;
    while(temporaryPointerToHeadNode->next->next !=NULL)
    {
        temporaryPointerToHeadNode = temporaryPointerToHeadNode->next;
    }
    free(temporaryPointerToHeadNode->next);
    temporaryPointerToHeadNode->next = NULL;
}
Node with specific data
-(void)deleteNode:(Node*)head
{
    Node *temporaryPointerToHeadNode = head;
    while(temporaryPointerToHeadNode->next->data != 5)
    {
        temporaryPointerToHeadNode = temporaryPointerToHeadNode->next;
    }
    Node *pointerToHoldTheNodeToDelete = temporaryPointerToHeadNode->next;
    temporaryPointerToHeadNode->next = temporaryPointerToHeadNode->next->next;
    free(pointerToHoldTheNodeToDelete);
}

4.Insert a linked list node

Given a pointer to head; a new node can be inserted at head, as the last node and after a specific data.

At head
-(void)insertList:(Node*)head
{
    Node *newNodeToInsert = (Node*)malloc(sizeof(Node));
    newNodeToInsert->data=11;
    newNodeToInsert->next=head;
    head= newNodeToInsert;
}
@end
As last node
-(void)insertList:(Node*)head
{
    Node *t=head;
    while(t->next) t= t->next;
    Node *newNodeToInsert = (Node*)malloc(sizeof(Node));
    newNodeToInsert->data=11;
    newNodeToInsert->next=NULL;
    t->next = newNodeToInsert;
}
@end
After a node with specific data
-(void)insertList:(Node*)head
{
    Node *t=head;
    while(t->data !=5) t= t->next;
    Node *newNodeToInsert = (Node*)malloc(sizeof(Node));
    newNodeToInsert->data=11;
    newNodeToInsert->next = t->next;
    t->next = newNodeToInsert;
}
@end

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *