Doubly Linked List Flashcards

Doubly Linked List: Like a two-way street, navigate forward and backward.

Key Terms:

Link: A car carrying data.

Next: Points to the next car.

Prev: Points to the previous car.

Linked List: The street connecting the first and last cars.

Doubly Linked List Representation

'First' and 'last' signs on the street.

Each car (link) has data and a 'next' sign.

Cars connected via 'next' and 'previous' signs.

Last car's 'next' sign is a dead end (NULL).

Basic Operations

Insertion:

InsertFirst: Add a car at the beginning.

InsertLast: Add a car at the end.

InsertAfter: Insert a car after a specific car.

Deletion:

Deletion: Remove the first car.

DeleteLast: Remove the last car.

Delete: Remove a specific car.

Display:

DisplayForward: View cars from start to end.

DisplayBackward: View cars from end to start.

Insertion at the Beginning

Create a new car with front, cargo, rear.

Load cargo.

If the street is empty, it's the only car.

Otherwise:

Link the existing first car to the new car's rear; set front to null.

Point the street to the new car.

Algorithm

START

Create a new car with front, cargo, rear.

Load cargo.

If empty, it's the only car.

Otherwise, link the first car to 'rear'; set 'front' to null.

Point the street to the new car.

END

C Implementation:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
  int data;
  int key;
  struct node *next;
  struct node *prev;
};

struct node *head = NULL;
struct node *last = NULL;
struct node *current = NULL;

bool isEmpty() {
  return head == NULL;
}

void printList() {
  struct node *ptr = head;

  while (ptr != NULL) {
    printf("(%d,%d) ", ptr->key, ptr->data);
    ptr = ptr->next;
  }
}

void insertFirst(int key, int data) {
  struct node *link = (struct node*) malloc(sizeof(struct node));

  link->key = key;
  link->data = data;

  if (isEmpty()) {
    last = link;
  } else {
    head->prev = link;
  }

  link->next = head;
  head = link;
}

void main() {
  insertFirst(1, 10);
  insertFirst(2, 20);
  insertFirst(3, 30);
  insertFirst(4, 1);
  insertFirst(5, 40);
  insertFirst(6, 56);

  printf("\nDoubly Linked List: ");
  printList();
}

Insertion at the End

If empty, add the car and point the street to it.

If not empty, find the last car.

Link the last car to the new car.

New car's rear is a dead end (NULL).

Algorithm

START

If empty, add the car and point the street to it.

If not empty, find the last car.

Link the last car to the new car.

New car's rear points to NULL.

END

C Implementation

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
    int data;
    int key;
    struct node *next;
    struct node *prev;
};

struct node *head = NULL;
struct node *last = NULL;
struct node *current = NULL;

bool isEmpty() {
    return head == NULL;
}

void printList() {
    struct node *ptr = head;
    while (ptr != NULL) {
        printf("(%d,%d) ", ptr->key, ptr->data);
        ptr = ptr->next;
    }
}

void insertFirst(int key, int data) {
    struct node *link = (struct node*) malloc(sizeof(struct node));
    link->key = key;
    link->data = data;
    if (isEmpty()) {
        last = link;
    } else {
        head->prev = link;
    }
    link->next = head;
    head = link;
}

void insertLast(int key, int data) {
    struct node *link = (struct node*) malloc(sizeof(struct node));
    link->key = key;
    link->data = data;
    if (isEmpty()) {
        last = link;
    } else {
        last->next = link;
        link->prev = last;
    }
    last = link;
}

void main() {
    insertFirst(1, 10);
    insertFirst(2, 20);
    insertFirst(3, 30);
    insertFirst(4, 1);
    insertLast(5, 40);
    insertLast(6, 56);
    printf("Doubly Linked List: ");
    printList();
}

Deletion at the Beginning

Remove the first car.

The street starts at the next car.

The link is removed.

Algorithm

START

Check the street status.

If empty, no cars to remove.

If not empty, start the street at

C Implementation

```c

include

include

include

struct node {
int data;
int key;
struct node *next;
struct node *prev;
};

struct node *head = NULL;
struct node *last = NULL;
struct node *current = NULL;

bool isEmpty() {
return head == NULL;
}

void printList() {
struct node *ptr = head;

while (ptr != NULL) {
printf("(%d,%d) ", ptr->key, ptr->data);
ptr = ptr->next;
}
}

void insertFirst(int key, int data) {
struct node link = (struct node) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if (isEmpty()) {
last = link;
} else {
head->prev = link;
}
link->next = head;
head = link;
}

struct node* deleteFirst() {
struct node *tempLink = head;
if (head->next == NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
return tempLink;
}

void main() {
insertFirst(1, 10);
insertFirst(2, 20);
insertFirst(3, 30);
insertFirst(4, 1);
insertFirst(5, 40);
insertFirst(6, 56);

printf("Doubly Linked List: \n");
printList();

deleteFirst();

printf("\nList after deleting first record: \n");