1 of 47

Linked Lists

Submitted By:-Mrs.Mehak Kapoor

Assistant Professor Computer Science & IT Dept.

2 of 47

Linked List

A linear collection of self- referential objects, called nodes, connected by other links

​

​

    • linear: for every node in the list, there is one and only one node that precedes it (except for possibly the first node, which may have no predecessor,) and there is one and only one node that succeeds it, (except for possibly the last node, which may have no successor)

​

    • self-referential: a node that has the ability to refer to another node of the same type, or even to refer to itself

​

3 of 47

    • node: contains data of any type, including a reference to another node of the same data type, or to nodes of different data types

​

    • Usually a list will have a beginning and an end; the first element in the list is accessed by a reference to that class, and the last node in the list will have a reference that is set to null

​

4 of 47

Declarations for Linked Lists

  • For this presentation, nodes in a linked list are objects, as shown here.

data_field

link_field

10

data_field

link_field

15

data_field

link_field

7

null

class node

{

public:

typedef double value_type;

...

private

value_type data_field;

node *link_field;

};

​

​

5 of 47

Declarations for Linked Lists

  • The data_field of each node is a type called value_type, defined by a typedef.

data_field

link_field

10

data_field

link_field

15

data_field

link_field

7

null

class node

{

public:

typedef int value_type;

...

private

value_type data_field;

node *link_field;

};

​

​

6 of 47

Declarations for Linked Lists

  • Each node also contains a link_field which is a pointer to another node.

data_field

link_field

10

data_field

link_field

15

data_field

link_field

7

null

class node

{

public:

typedef int value_type;

...

private

value_type data_field;

node *link_field;

};

​

​

7 of 47

Declarations for Linked Lists

  • A program can keep track of the front node by using a pointer variable such as head_ptr in this example.
  • Notice that head_ptr is not a node -- it is a pointer to a node.

head_ptr

data_field

link_field

10

data_field

link_field

15

data_field

link_field

7

null

8 of 47

Declarations for Linked Lists

  • A program can keep track of the front node by using a pointer variable such as head_ptr.
  • Notice that head_ptr is not a node -- it is a pointer to a node.
  • We represent the empty list by storing null in the head pointer.

head_ptr

null

9 of 47

Inserting a Node at the Front

We want to add a new entry, 13, to the front of the linked list shown here.

void list_head_insert(node*& head_ptr, const node::value_type& entry);

10

15

7

null

head_ptr

entry

13

10 of 47

Inserting a Node at the Front

  • Create a new node, pointed to by a local variable insert_ptr.

10

15

7

null

head_ptr

entry

13

insert_ptr

void list_head_insert(node*& head_ptr, const node::value_type& entry);

11 of 47

Inserting a Node at the Front

  • insert_ptr = new node;

10

15

7

null

head_ptr

entry

13

insert_ptr

void list_head_insert(node*& head_ptr, const node::value_type& entry);

12 of 47

Inserting a Node at the Front

10

15

7

null

head_ptr

entry

13

insert_ptr

13

    • insert_ptr = new node;
    • Place the data in the new node's data_field.

void list_head_insert(node*& head_ptr, const node::value_type& entry);

13 of 47

Inserting a Node at the Front

10

15

7

null

head_ptr

entry

13

insert_ptr

13

    • insert_ptr = new node;
    • Place the data in the new node's data_field.
    • Connect the new node to the front of the list.

void list_head_insert(node*& head_ptr, const node::value_type& entry);

14 of 47

Inserting a Node at the Front

The correct new node can be completely created in one step by calling an appropriate node constructor.

10

15

7

null

head_ptr

entry

13

insert_ptr

13

    • insert_ptr = new node(entry, head_ptr);

void list_head_insert(node*& head_ptr, const node::value_type& entry);

15 of 47

Inserting a Node at the Front

10

15

7

null

head_ptr

entry

13

insert_ptr

13

    • insert_ptr = new node(entry, head_ptr);
    • Make the old head pointer point to the new node.

void list_head_insert(node*& head_ptr, const node::value_type& entry);

16 of 47

Inserting a Node at the Front

10

15

7

null

head_ptr

entry

13

insert_ptr

13

    • insert_ptr = new node(entry, head_ptr);
    • head_ptr = insert_ptr;

void list_head_insert(node*& head_ptr, const node::value_type& entry);

17 of 47

Inserting a Node at the Front

  • insert_ptr = new node(entry, head_ptr);
  • head_ptr = insert_ptr;

10

15

7

null

head_ptr

13

When the function returns, the

linked list has a new node at the

front.

void list_head_insert(node*& head_ptr, const node::value_type& entry);

18 of 47

Inserting a Node at the Front

void list_head_insert(node*& head_ptr, const node::value_type& entry)

{

node *insert_ptr;

​

insert_ptr = new node(entry, head_ptr);

head_ptr = insert_ptr;

}

19 of 47

Inserting a Node at the Front

void list_head_insert(node*& head_ptr, const node::value_type& entry)

{

node *insert_ptr;

​

insert_ptr = new node(entry, head_ptr);

head_ptr = insert_ptr;

}

Does the function work

correctly for the empty

list ?

20 of 47

Inserting a Node at the Front

head_ptr

entry

13

null

Does the function work

correctly for the empty

list ?

void list_head_insert(node*& head_ptr, const node::value_type& entry)

{

node *insert_ptr;

​

insert_ptr = new node(entry, head_ptr);

head_ptr = insert_ptr;

}

21 of 47

Inserting a Node at the Front

head_ptr

entry

13

null

insert_ptr

13

void list_head_insert(node*& head_ptr, const node::value_type& entry)

{

node *insert_ptr;

​

insert_ptr = new node(entry, head_ptr);

head_ptr = insert_ptr;

}

null

22 of 47

Inserting a Node at the Front

head_ptr

entry

13

insert_ptr

13

null

void list_head_insert(node*& head_ptr, const node::value_type& entry)

{

node *insert_ptr;

​

insert_ptr = new node(entry, head_ptr);

head_ptr = insert_ptr;

}

23 of 47

Inserting a Node at the Front

head_ptr

13

null

void list_head_insert(node*& head_ptr, const node::value_type& entry)

{

node *insert_ptr;

​

insert_ptr = new node(entry, head_ptr);

head_ptr = insert_ptr;

}

When the function

returns, the linked list

has one node.

24 of 47

Caution!

  • Always make sure that your linked list functions work correctly with an empty list.

EMPTY LIST

25 of 47

Pseudocode for Inserting Nodes

  • Nodes are often inserted at places other than the front of a linked list.
  • There is a general pseudocode that you can follow for any insertion function. . .

26 of 47

Pseudocode for Inserting Nodes

  • Determine whether the new node will be the first node in the linked list. If so, then there is only one step:

list_head_insert(head_ptr, entry);

27 of 47

Pseudocode for Inserting Nodes

  • Determine whether the new node will be the first node in the linked list. If so, then there is only one step:

The function

we already wrote

list_head_insert(head_ptr, entry);

28 of 47

Pseudocode for Inserting Nodes

  • Determine whether the new node will be the first node in the linked list. If so, then there is only one step:

list_head_insert(head_ptr, entry);

A pointer

to the

head of

the list

29 of 47

Pseudocode for Inserting Nodes

  • Determine whether the new node will be the first node in the linked list. If so, then there is only one step:

list_head_insert(head_ptr, entry);

The data to put

in the new node

30 of 47

Pseudocode for Inserting Nodes

  • Otherwise (if the new node will not be first):
  • Start by setting a pointer named previous_ptr to point to the node which is just before the new node's position.

31 of 47

Pseudocode for Inserting Nodes

15

10

7

null

head_ptr

  • Otherwise (if the new node will not be first):
  • Start by setting a pointer named previous_ptr to point to the node which is just before the new node's position.

In this example, the

new node will be

the second node

previous_ptr

32 of 47

Pseudocode for Inserting Nodes

15

10

7

null

head_ptr

  • Otherwise (if the new node will not be first):
  • Start by setting a pointer named previous_ptr to point to the node which is just before the new node's position

Look at the pointer

which is in the node

*previous_ptr

previous_ptr

33 of 47

Pseudocode for Inserting Nodes

15

10

7

null

head_ptr

  • Otherwise (if the new node will not be first):
  • Start by setting a pointer named previous_ptr to point to the node which is just before the new node's position

This pointer is called

previous_ptr->link_field

(although this name may

be private to the node)

previous_ptr

34 of 47

Pseudocode for Inserting Nodes

15

10

7

null

head_ptr

  • Otherwise (if the new node will not be first):
  • Start by setting a pointer named previous_ptr to point to the node which is just before the new node's position

previous_ptr->link_field

points to the head

of a small linked

list, with 10 and 7

previous_ptr

35 of 47

Pseudocode for Inserting Nodes

15

10

7

null

head_ptr

  • Otherwise (if the new node will not be first):
  • Start by setting a pointer named previous_ptr to point to the node which is just before the new node's position.

The new node must

be inserted at the

front of this small

linked list.

13

previous_ptr

36 of 47

Pseudocode for Inserting Nodes

15

10

7

null

head_ptr

  • Otherwise (if the new node will not be first):
  • Start by setting a pointer named previous_ptr to point to the node which is just before the new node's position.

13

previous_ptr

list_head_insert(previous_ptr->link_field, entry);

37 of 47

Pseudocode for Inserting Nodes

Use a node member function to get the link field if needed.

15

10

7

null

head_ptr

  • Otherwise (if the new node will not be first):
  • Start by setting a pointer named previous_ptr to point to the node which is just before the new node's position.

13

previous_ptr

list_head_insert(previous_ptr->link( ), entry);

38 of 47

Pseudocode for Inserting Nodes

  • Determine whether the new node will be the first node in the linked list. If so, then there is only one step:

list_head_insert(head_ptr, entry);

  • Otherwise (if the new node will not be first):
  • Set a pointer named previous_ptr to point to the node which is just before the new node's position.
  • Make the function call:

list_head_insert(previous_ptr->link( ), entry);

39 of 47

Pseudocode for Inserting Nodes

  • The process of adding a new node in the middle of a list can also be incorporated as a separate function. This function is called list_insert in the linked list toolkit of Section 5.2.

40 of 47

Pseudocode for Removing Nodes

  • Nodes often need to be removed from a linked list.
  • As with insertion, there is a technique for removing a node from the front of a list, and a technique for removing a node from elsewhere.
  • We’ll look at the pseudocode for removing a node from the front of a linked list.

41 of 47

Removing the Head Node

10

15

7

null

head_ptr

13

  • Start by setting up a temporary pointer named remove_ptr to the head node.

remove_ptr

42 of 47

Removing the Head Node

10

15

7

null

head_ptr

13

  • Set up remove_ptr.
  • head_ptr = remove_ptr->link( );

​

remove_ptr

Draw the change that this statement will make to the linked list.

43 of 47

Removing the Head Node

10

15

7

null

head_ptr

13

  • Set up remove_ptr.
  • head_ptr = remove_ptr->link( );

remove_ptr

44 of 47

Removing the Head Node

​

  • Set up remove_ptr.
  • head_ptr = remove_ptr->link( );
  • delete remove_ptr; // Return the node's memory to heap.

10

15

7

null

head_ptr

13

remove_ptr

45 of 47

Removing the Head Node

Here’s what the linked list looks like after the removal finishes.

10

15

7

null

head_ptr

46 of 47

Summary

  • It is easy to insert a node at the front of a list.
  • The linked list toolkit also provides a function for inserting a new node elsewhere
  • It is easy to remove a node at the front of a list.
  • The linked list toolkit also provides a function for removing a node elsewhere--you should read about this function and the other functions of the toolkit.

47 of 47

​

THANK YOU!