Linked List

List

• collection of variable number of data items
• Each item: nodes
• Most commonly used non-primitive data structure
  

  

Operation on Linked List

• creating, traversing, inserting, deleting, searching, merging
  

  

  
  (새로운 노드를 연결할 때 null을 가리키는 next를 다음 노드로 연결)

Creating a Linked List

struct Node
{
int info'
struct Node *next;
}

• 구조체로 연결

Inserting a Node into the Linked List

Inserting in the Beginning

void insertBeginning (struct node** head, int new_info) {
/* 1. create a new empty node */
struct node* new_node = (struct Node*) malloc(sizeof(struct node));
/*allocates the requested memory and returns a pointer to it */

/* 2. put in the data */
new_node->info = new_info;

/* 3. Make next of new node point to where head was pointing to that is to the first node of the previous list */

new_node->next = (*head);
/* 4. move the head to point to the new node */
(*head) = new_node;
}

Inserting After a Given Node

void insertAfter(struct node* given_node, int new_info) 
{
if (given_node == NULL) /*1. check if the given node is NULL */ 
{
	printf(“ERROR! The given node cannot be NULL"); 
	return;
}
struct node* new_node =(struct node*) malloc(sizeof(struct node)); /* 2. allocate new node */
new_node->info = new_info; /* 3. put in the data */
new_node->next = given_node->next; /* 4. Make next of new node as next of prev_node */
given_node->next = new_node; /* 5. move the next of prev_node as new_node */
}

Inserting at the End

void insertEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); /* 1. allocate node */
struct Node *last = *head_ref; /* Copy the head node */ 
new_node->data = new_data; /* 2. put in the data */
new_node->next = NULL;/* 3. New node = last node, make next = NULL*/
if (*head_ref == NULL) /* 4. If the Linked List is empty, then make the new node as head */
{
*head_ref = new_node; return;
}
while (last->next != NULL) last = last->next;/* 5. Else traverse till the last node */
last->next = new_node; /* 6. Change the next of last node */
}

Deleting a Node from the Linked List

Deleting a Node from the Beginning

1. Make second node as head
2. Delete memory allocated for first node

Deleting a Node From a Given Position

1. Find previous node of the target node(node to be deleted)
2. Change the next of previous node to next to the given node
3. Free memory for the node to be deleted

Deleting Node from the End

1.If the first node is null or there is only one node, then return null
if headNode == null then return null
if headNode.nextNode == null then free head and return null
2. Traverse the linked list till the second last node
while secondLast.nextNode.nextNode != null secondLast = secondLast.nextNode
3. Delete the last node, i.e. the next node of the second last node delete (secondLast.nextNode)
Set the value of next of second last node to null

Types of Lists

Singly Linked List(SLL)

• information : data
• link or next: memory address
• navigtion: forward
  Only one link field in each node

Single Circular Linked List

• last item contains link of the first element as next
• first element has a link to the last elementt as previous
• every node is accessibel from any node

Doubly Linked List

• Items can be navigated forward and backward
• points: next, previous
• three parts
  Next : address of the next node
  Previous : address of the previous node
  Information : Actual Data
• if previous=NULL : first node
• if next=NULL : last node

struct Node
{
	int data;
    struct Node *next;
    struct Node *prev;
};

Doubly Circulart Linked List

• three parts
  Next : address of the next node
  Previous : address of the previous node
  Information : Actual Data
• next of the last node points to the first node
• previous of the first node points to the last node

Singly vs Doubly

advantages over singly linked list

• dll can be traversed in both forward and backward direction
• the delete operation in DLL is more efficient (if pointer to the node to be deleted is given )
• quickly insert a new node before a given node

disadvantages over singly linked list

• every node of dll require extra space for an previous pointer
• all operations require an extra pointer previous to be maintained

DLL : Insertion in the Beginning

void insertBeginningDouble(struct node** head, int new_info) 
{
	struct node* new_node = (struct node*)malloc(sizeof(struct node)); 		new_node->data = new_info;
    new_node->next = (*head);
    new_node->prev = NULL;
    if ((*head) != NULL)
    	(*head)->prev = new_node;
    (*head) = new_node;
}

DLL : Insertion at the End

void insertEndDouble(struct node** head_ref, int new_info) 
{
	struct node* new_node = (struct Node*)malloc(sizeof(struct node)); 		struct node* last = *head;
	new_node->info = new_info;
	new_node->next = NULL;
	if (*head == NULL) 
    	{
		new_node->prev = NULL; 
        *head = new_node; 
        return;
		}
	while (last->next != NULL) last = 
    	last->next;
    last->next = new_node;
	new_node->prev = last; 
    return;
}

Insertion after a Given Node

void insertAfter(struct node* given_node, int new_info) 
{
	if (given_node == NULL) { 
    	printf(“error! cannot be NULL");
	return; 
    }
    struct node* new_node = (struct Node*)malloc(sizeof(struct node)); 		new_node->info = new_info;
	new_node->next = given_node->next;
	given_node->next = new_node;
	new_node->prev = given_node; 
    if (new_node->next != NULL)
    	new_node->next->prev = new_node;
}

Insertion before a Given Node

void insertBefore(struct node** head, struct node* next_node, int new_info) 
{
	if (next_node == NULL) {
		printf("the given next node cannot be NULL"); 
        return;
	}
    struct node* new_node = (struct node*)malloc(sizeof(struct node)); 		new_node->info = new_info;
    new_node->prev = next_node->prev;
    next_node->prev = new_node;
    new_node->next = next_node;
    if (new_node->prev != NULL)
		new_node->prev->next = new_node;
	else
		(*head) = new_node; 
}

Deletion from Beginning, Middle and End

void deleteNode(struct node** head, struct node* target) 
{
	if (*head == NULL || target == NULL) 
    	return;
	if (*head == target)
		*head = target->next;
	if (target->next != NULL) 
    	target->next->prev = target->prev;
	if (target->prev != NULL) 
    	target->prev->next = target->next;
			free(del); 
   	return;
}