Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

1 embedded_system

Embedded System
PART 9(Data Structure)
LIFO (STACK)
FIFO (QUEU)
Linked List

[Link] SHENOUDA
Learn in Depth
[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

2 embedded_system

Introduction to Data Structures

LEARN-IN-DEPTH
Be professional in
embedded system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

3
Introduction to Data Structures
embedded_system

 Data Structure is a way of collecting and organizing data in such a way that we can perform operations on these data in
an effective way.

 data structures for embedded systems.

 All embedded systems need to store data.
 That data can take on many different forms.
 Data can represent sensor information, control information for things like motors, or status information for active processes.
 Typically, when you think of data, you should think of variables. Variables are individual storage containers that you have one specific
type.
 However, you will often want to store lots of variables, and often associate one variable with another.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

There are a subset of data structures that are

#Be_professional_in

4 embedded_system

used very regularly in embedded systems

 LIFO (Last-In-First-Out) buffer. (Stack)
 Circular/FIFO (First-In-First-Out) buffer. (Queue)
 linked list – Single, Doubly and Circular.

Interface methods allow for operation on a structure including:

 Adding New Data

 Removing Data

 Initialize a Structure

 Clearing a Structure

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

5 embedded_system

LIFO Buffer
LEARN-IN-DEPTH
Be professional in
embedded system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

6
LIFO Buffers
embedded_system

 LAST-In-First-Out (LIFO)

 Also referred to as a stack END

 Similar to processor stack, but different.

 Adds and removes data items to and from the same

end
Head (Add)
Head (current)
Base = ?
Head (Remove)
Head = ?
Length = ?

LIFO Buffer Structure

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH
Base = Bottom #Be_professional_in

7
LIFO Buffer Example
embedded_system
Head = Temp1
count= 1
Base temp1
LIFO Buffer Structure head
 Temp1 = get_temp();
 Buffer_add(temp1);

Data Buffer

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH
Base = Bottom #Be_professional_in

8
LIFO Buffer Example
embedded_system
Head = Temp2
count= 2
Base temp1
LIFO Buffer Structure
temp2
 Temp1 = get_temp();
head
 Buffer_add(temp1);
 Temp2 = get_temp();
Data Buffer
 Buffer_add(temp2);

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH
Base = Bottom #Be_professional_in

9
LIFO Buffer Example
embedded_system
Head = Temp3
count= 3
Base temp1
LIFO Buffer Structure
temp2
 Temp1 = get_temp();
temp3
 Buffer_add(temp1); head
 Temp2 = get_temp();
Data Buffer
 Buffer_add(temp2);
 Temp3 = get_temp();
 Buffer_add(temp3);

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH
Base = Bottom #Be_professional_in

10
LIFO Buffer Example
embedded_system
Head = Temp2
count= 2
Base temp1
LIFO Buffer Structure
temp2
 Temp3 = Buffer_pop();
head Old data

Data Buffer

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH
Base = Bottom #Be_professional_in

11
LIFO Buffer Example
embedded_system
Head = Temp1
count= 1
Base temp1
LIFO Buffer Structure head Old data
 Temp3 = Buffer_pop();
Old data
 Temp2 = Buffer_pop();

Data Buffer

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH
Base = Bottom #Be_professional_in

12
LIFO Buffer Example
embedded_system
Head = Temp4
count= 2
Base temp1
LIFO Buffer Structure temp4
 Temp3 = Buffer_pop();
head Old data
 Temp2 = Buffer_pop();
 Temp4 = get_temp();
Data Buffer
 Buffer_add(temp4);

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

13
LIFO Structure
embedded_system

 Items to track
 Starting point in memory (BASE)

 Total Size of buffer (Length)

 Total Number of added items (Count)

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

14
Stacks
embedded_system

 Stack is an abstract data type with a bounded(predefined) capacity. It is a

simple data structure that allows adding and removing elements in a particular
order. Every time an element is added, it goes on the top of the stack, the only
element that can be removed is the element that was at the top of the stack,
just like a pile of objects.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

15
Basic features of Stack
embedded_system

 Stack is an ordered list of similar data type.

 Stack is a LIFO structure. (Last in First out).
 push() function is used to insert new elements into the Stack and pop() is used
to delete an element from the stack. Both insertion and deletion are allowed
at only one end of Stack called Top.
 Stack is said to be in Overflow state when it is completely full and is said to be
in Underflow state if it is completely empty.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

16
Applications of Stack
embedded_system

 The simplest application of a stack is to reverse a word. You push a given word
to stack - letter by letter - and then pop letters from the stack.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

17
Implementation of Stack
embedded_system

 Stack can be easily implemented using an Array or a Linked List. Arrays are
quick, but are limited in size and Linked List requires overhead to allocate, link,
unlink, and deallocate, but is not limited in size. Here we will implement Stack
using array.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

18
Stack Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

19
Stack Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

20
Stack Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

21
Stack Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

22
Stack Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

23
Stack Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

24
Stack Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

25
Stack Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

26
Stack Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

27
Status of Stack
embedded_system

Position of Top Status of Stack

-1 Stack is Empty
0 Only one element in Stack
N-1 Stack is Full
N Overflow state of Stack

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

28 embedded_system

LIFO (Stack) implementation using Dynamic/Static

Allocation
HTTPS://[Link]/KEROLES/EMBEDDED_SYSTEM/BLOB/MASTER/C_PROGRAMMIN
G/EMBEDDED%20SYSTEM%20PART%209(DATA%20STRUCTURE)
LEARN-IN-DEPTH
Be professional in
embedded system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

29 embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

Initialization (Dynamic/Static Allocation)

#Be_professional_in

30 embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

31
Buffer FULL
embedded_system

Base
???
???

???

???
???
head
First_buffer
(SRAM)

Base = 0x100
Head = 0x100
Length = 5

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

32
Buffer ADD (Push)
embedded_system

Base
item1
??? head
???

???
???
First_buffer
(SRAM)

Base = 0x100
Head = 0x100
Length = 5

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

33
Buffer (POP)
embedded_system

Base
Old value head
???

???

???
???
First_buffer
(SRAM)

Base = 0x100
Head = 0x100
Length = 5

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

34 embedded_system

Circular Buffer & FIFOS

LEARN-IN-DEPTH
Be professional in
embedded system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

35 embedded_system

Embedded Input / Output

 Buffers are used in most embedded programs, either as a software or
hardware implementation.
 An example could be an interrupt service routine that writes out
serial data, similar to our printf function. And a program that wants to print
out a lot of data. To print data we often use a UART.
 This will only write out a single byte per transaction and usually at a very slow
rate like a 100 kilobits per second.
 Typically you wouldn't send just one byte, you would send numerous. And
instead of sitting there blocking, sending byte after byte, you may have a small
function that is totally responsible for shifting out bytes when we're ready.
This would allow your main, or your main process, to focus on other
processing. In this example, we would likely use a circular buffer, or a FIFO-like
tx
buffer, to store our character string to transmit. And an interrupt sub-routine to
pull that data out.
 This would allow your main, or your main process, to focus on other
processing.

[Link]
 Follow us

Press
Base = ? here
#LEARN_IN DEPTH

Tail = ? #Be_professional_in

36
Circular Buffer
embedded_system

Head=?
Length=?
FIFO Circular Buffer

 Is an example of a First-In-First-
end end end
Out (FIFO) Buffer
head item
 Adds data to one end (Head) (ADD)head item
item
 Removes data items from the item item
item
other end (Tail) (Remove (Remove)
2items) item Tail item
 Head and Tail will wrap around item
Tail empty
when boundary reached item empty
Base head item
Base item empty Base
Tail
Circular Circular
Circular
Buffer Buffer
Buffer

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

37 embedded_system

Logic Sequence
 Head =3
 Head & Tail pint to  Head =1
 Count =3
Base end  Count =1 end  Buffer_add(&buf,0xff);
end
 Buffer_add(&buf,0xff);
 Count =0  Buffer_add(&buf,0x12);
empty empty empty
 Length =5  Buffer_add(&buf,0x34);
empty empty head empty

empty empty 0x43

empty head empty 0x12

head 0xff 0xff
Base empty Base Base
Tail Tail Tail
Circular Circular Circular
Buffer Buffer Buffer

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

38 embedded_system

Logic Sequence
 Head =3  Head =0
 Count =2
end
end  Count =4
 Tail =1  Length =5 0x12
 Buffer_add(&buf,0xff); empty  Tail =1
0x12
 Buffer_add(&buf,0x12);  Buffer_add(&buf,0xff);
head empty
 Buffer_add(&buf,0x34);  Buffer_add(&buf,0x12);
0x43
0x43
 Buffer_ren(&buf,&team)  Buffer_add(&buf,0x34); 0x12
Tail
Tail 0x12  Buffer_ren(&buf,&team) head empty
 Buffer_add(&buf,0x12); Base
Base empty
 Buffer_add(&buf,0x12); Circular
Circular Buffer
Buffer

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

39
Queue
embedded_system

 Queue is an abstract data structure, somewhat similar to Stack. In contrast to

Queue, queue is opened at both end. One end is always used to insert data
(enqueue) and the other is used to remove data (dequeue). Queue follows
First-In-First-Out methodology, i.e., the data item stored first will be accessed
first.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

40
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

41
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

42
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

43
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

44
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

45
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

46
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

47
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

48
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

49
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

50
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

51
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

52
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

53
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

54
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

55
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

56
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

57
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

58
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

59
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

60
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

61
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

62
Queue Implementation with Array
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

63 embedded_system

Circular Buffer & FIFOS (queue) implementation using

Dynamic/Static Allocation
HTTPS://[Link]/KEROLES/EMBEDDED_SYSTEM/COMMIT/7A2BA4F3500117BEDDB
B10F2EEA93796B99DFFCC
LEARN-IN-DEPTH
Be professional in
embedded system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

64 embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

65 embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

66 embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

67 embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

68 embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

69 embedded_system

Linear Vs Non-Linear Data Structure

LEARN-IN-DEPTH
Be professional in
embedded system

[Link]
 Follow us

Press

Linear Vs Non-Linear Data

here
#LEARN_IN DEPTH

#Be_professional_in

70 embedded_system

Structure
 linear data structures
 which means that there is a
sequence and an order to how they
are constructed sequentially
 Examples: arrays and linked lists

 non-linear data structures

 items don’t have to be arranged in
order, which means that we could
arrange the data structure non-
sequentially.
 Examples: Trees and graphs

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

71 embedded_system

Linked List
LEARN-IN-DEPTH
Be professional in
embedded system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

72
Data Structure - Linked List
embedded_system

 A linked list is a linear data structure where each element is a separate object.
 A linked-list is a sequence of data structures which are connected together via links.
 Link − Each Link of a linked list can store a data called an element.
 Next − Each Link of a linked list contain a link to next link called Next.
 LinkedList − A LinkedList contains the connection link to the first Link called First.
 Linked list can be visualized as a chain of nodes, where every node points to the next node.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

73
Types of Linked List
embedded_system

 Simple Linked List − Item Navigation is

forward only.
 Doubly Linked List − Items can be navigated
forward and backward way.
 Circular Linked List − Last item contains link
of the first element as next and and first
element has link to last element as prev.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

74 embedded_system

In you opinion what is the difference between arrays and

linked list according to (memory point of view)
THINK IN DEPTH 
LEARN-IN-DEPTH
Be professional in
embedded system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

75
Memory Allocation (Array Vs Linked List)
embedded_system

 The fundamental difference between arrays and

linked lists is that
 arrays are static data structures, while linked lists
are dynamic data structures. A static data
structure needs all of its resources to be allocated
when the structure is created;
 On the other hand, a dynamic data structure can
shrink and grow in memory. It doesn’t need a set
amount of memory to be allocated in order to
exist, and its size and shape can change, and the
amount of memory it needs can change as well.
 linked list to have its memory scattered
everywhere

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

76
Linked List Basic Operations
embedded_system

 Insertion − add an element at the beginning of the list.

 Deletion − delete an element at the beginning of the list.
 Display − displaying complete list.
 Search − search an element using given key.
 Delete − delete an element using given key.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

77
Insertion Operation
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

78
Deletion Operation
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

79
Reverse Operation
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

80
Data Structure - Doubly Linked List
embedded_system

 Doubly Linked List is a variation of Linked list in which navigation is possible in

both ways either forward and backward easily as compared to Single Linked
List
 Doubly LinkedList contains an link element called first and last.
 Each Link carries a data field(s) and a Link Field called next.
 Each Link is linked with its next link using its next link.
 Each Link is linked with its previous link using its prev link.
 Last Link carries a Link as null to mark the end of the list.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

81
Singly Linked List as Circular
embedded_system

 In singly linked list, the next pointer of the last node points to the first node.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

82
Doubly Linked List as Circular
embedded_system

 n doubly linked list, the next pointer of the last node points to the first node
and the previous pointer of the first node points to the last node making the
circular in both directions.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

83
Dynamic Linked Lists
embedded_system

 Problem Statement
Consider Students Database program, it appears that the program uses (realloc)
when
adding or deleting student member. Using (realloc) may solve the problem,
especially if
the structure size and the number of records are small.
Actually (realloc) function
1. Creates a new buffer with the new size
2. Copies the original contents
3. Deletes the original buffer
4. Returns the address of the new buffer
Consider a complicated SStudent structure containing all student information and
his courses
degrees as shown below:

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

84
Dynamic Linked Lists Contn.
embedded_system

Above structure size is 8548 byte, if it is required to build a

program that supports up to
10,000 student. This means adding extra student will cost
transfering following data size
inside the computer:
10000 * 8548 = 85,480,000 Byte
If it is required to transfere 1 byte 1 micosecond the above
addition operation will take 85
second or 1.5 minute. This time is very long.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

85
Understanding the Solution
embedded_system

 Another techniqe is used, it depends on storing student information in a

separte buffers and
linking between them using a pointers. This techniqe called the Linked List
method.
Assument the new structure SStudent after adding the member (SStudent
*pNextStudent). pNextStudent is a pointer containing the address of the next
member of the list. Last member of the last have equals pNextStudent NULL.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

86 embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

87
Write the Program
embedded_system

 At the beginning of the program only it is required to have one empty pointer,
indicating that
there is no students added.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

88 embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

89 embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

90
To delete certain record to the list:
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

91 embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

92
ViewStudents function:
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

93
DeleteAll function:
embedded_system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

94 embedded_system

Linked List (Thinking question)

LEARN-IN-DEPTH
Be professional in
embedded system

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

95 embedded_system

Write a function to get Nth node in a Linked List

 Write a GetNth() function that takes a linked list and an integer index and returns
the data value stored in the node at that index position.
 Example:
 Input: 1->10->30->14, index = 2
 Output: 30
 The node at index 2 is 30
 Solution:
1. Initialize count = 0
2. Loop through the link list
a. if count is equal to the passed index then return current
node
b. Increment count
c. change current to point to next of the current.

[Link]
 Follow us

Press

Find Length of a Linked List

here
#LEARN_IN DEPTH

#Be_professional_in

96 embedded_system

(Iterative and Recursive)

 Write a function to count the number of nodes in a given singly linked list.

[Link]
 Follow us

Press

Find Length of a Linked List

here
#LEARN_IN DEPTH

#Be_professional_in

97 embedded_system

(Iterative and Recursive)

 Write a function to count the number of nodes in a given singly linked list.

[Link]
 Follow us

Press

Program for n’th node from the end

here
#LEARN_IN DEPTH

#Be_professional_in

98 embedded_system

of a Linked List
 Given a Linked List and a number n, write a function that returns the value at
the n’th node from end of the Linked List.
 For example, if input is below list and n = 3, then output is “B”

[Link]
 Follow us

Press

Program for n’th node from the end

here
#LEARN_IN DEPTH

#Be_professional_in

99 embedded_system

of a Linked List
 Given a Linked List and a number n, write a function that returns the value at
the n’th node from end of the Linked List.
 For example, if input is below list and n = 3, then output is “B”

[Link]
 Follow us

Program for n’th node

Press
here
#LEARN_IN DEPTH

#Be_professional_in

from the end of a Linked 100 embedded_system

List
 Method 2 (Use two pointers)
Maintain two pointers – reference pointer
and main pointer.
 Initialize both reference and main pointers
to head.
 First, move reference pointer to n nodes
from head.
 Now move both pointers one by one until
the reference pointer reaches the end.
Now the main pointer will point to nth
node from the end. Return the main
pointer.
 Below image is a dry run of the above
approach:

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

101 embedded_system

Find the middle of a given linked list

 Given a singly linked list, find middle of the linked list. For example, if given
linked list is 1->2->3->4->5 then output should be 3.
 If there are even nodes, then there would be two middle nodes, we need to
print second middle element. For example,
if given linked list is 1->2->3->4->5->6 then output should be 4.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

102 embedded_system

Find the middle of a given linked list

 Method 1:
Traverse the whole linked list and
count the no. of nodes. Now
traverse the list again till count/2
and return the node at count/2.

 Method 2:
Traverse linked list using two
pointers. Move one pointer by one
and other pointer by two. When
the fast pointer reaches end slow
pointer will reach middle of the
linked list.
[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

103
How to Detect loop in a linked list
embedded_system

 Given a linked list, check if the linked list has loop or not. Below diagram
shows a linked list with a loop.

[Link]
 Follow us

Press

How to Detect loop

here
#LEARN_IN DEPTH

#Be_professional_in

104 embedded_system

in a linked list
 Given a linked list, check if the linked list has
loop or not. Below diagram shows a linked
list with a loop.
 Floyd’s Cycle-Finding Algorithm: This is the
fastest method and has been described
below:
 Traverse linked list using two pointers.

 Move one pointer(slow_p) by one and

another pointer(fast_p) by two.
 If these pointers meet at the same node then
there is a loop. If pointers do not meet then
linked list doesn’t have a loop
[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

105
Reverse a linked list
embedded_system

 Given pointer to the head node of a linked list, the task is to reverse the linked
list. We need to reverse the list by changing links between nodes.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

106
Reverse a linked list
embedded_system

 Given pointer to the head node of a linked list, the task is to reverse the linked
list. We need to reverse the list by changing links between nodes.

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

107
References
embedded_system

 [Link]
 [Link]
 std::printf, std::fprintf, std::sprintf, std::snprintf…..
 C Programming for Engineers, Dr. Mohamed Sobh
 C programming expert.
 [Link]/c-programming
 C programming Interview questions and answers
 C – Preprocessor directives
 [Link]
 [Link]
 [Link]

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

108 embedded_system

useful references for

C and Embedded C

[Link]
 Follow us

Press
here
#LEARN_IN DEPTH

#Be_professional_in

109 embedded_system

[Link]