Singly-linked list

## Linked list is a very important dynamic data structure. Basically, there are two types of linked list, singly-linked list and doubly-linked list. In a singly-linked list every element contains some data and a link to the next element, which allows to keep the structure. On the other hand, every node in a doubly-linked list also contains a link to the previous node. Linked list can be an underlying data structure to implement stack, queue or sorted list.

## Example

Sketchy, singly-linked list can be shown like this:Each cell is called a

**node**of a singly-linked list. First node is called

**head**and it’s a dedicated node. By knowing it, we can access every other node in the list. Sometimes, last node, called

**tail**, is also stored in order to speed up add operation.

## Operations on a singly-linked list

Concrete implementation of operations on the singly-linked list depends on the purpose, it is used for. Following the links below, you can find descriptions of the common concepts, proper for every implementation## A Simple Stack Question

I just started to learn stacks. How can I count the number of Items**in**a

**stack**by using ADT

**stack**operations?? Can u help me?

**ans**

>empty auxiliary stacks are available.

Getting information out of you people is like pulling teeth. Did you know that? I’ll assume that you can only use push, pop, and empty.

**In**that case, pop every item

**in**the

**stack**, increment a counter and push that item onto a second

**stack**. When the first

**stack**is empty, do the reverse but don’t increment the counter and you’ll have the same

**stack**that you started with.

1

- One way to think about this implementation is to think of functions as being stacked on top of each other; the last one added to the stack is the first one taken off. In this way, the data structure itself enforces the proper order of calls. Conceptually, a stack is simple: a 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.Consequently, a stack is said to have “first in last out” behavior (or “last in, first out”). The first item added to a stack will be the last item removed from a stack. So what’s the big deal? Where do stacks come into play? As you’ve already seen, stacks are a useful way to organize our thoughts about how functions are called. In fact, the “call stack” is the term used for the list of functions either executing or watiing for other functions to return. In a sense, stacks are part of the fundamental language of computer science. When you want to express an idea of the “first in last out” variety, it just makes sense to talk about it using the common terminology. Moreover, such operations show up an awful lot, from theoretical computer science tools such as a push-down automaton to AI, including implementations of depth-first search.Stacks have some useful terminology associated with them:

- Push To add an element to the stack
- Pop To remove an element from the stock
- Peek To look at elements in the stack without removing them
- LIFO Refers to the last in, first out behavior of the stack
- FILO Equivalent to LIFO

- [Prologue] Save the parameters, Local Variables and return address.
- [Body] If the base criterion has been reached, then perform the final computation and go to step 3; otherwise, perfprm the partial computation and go to step 1(initialize a recursive call)
- [Epilogue] Restore the most recently saved parameters, local variables, and return address. Go to this return address.
**simple program is given below**- #include <iostream>

#include <stack>

**using**namespace std;**int**main()

{

stack<**char**> stackObject;

stackObject.push(‘A’);

stackObject.push(‘B’);

stackObject.push(‘C’);

stackObject.push(‘D’);

**while**(!stackObject.empty()) {

cout << “Popping: ”;

cout << stackObject.top() << endl;

stackObject.pop();

}

**return**0;

}

## Data structure Queue:-)

♦ Is like a queue in the Mensa

♦ FIFO (ﬁrst in ﬁrst out): the ﬁrst one in is the ﬁrst one out

♦ Allows in O(1)

♦ Pushing an element to the end of the queue

♦ Accessing the ﬁrst and last element

♦ Removing the ﬁrst element

**Array-Based Queues**

The array-based queue is somewhat tricky to implement effectively. A simple con-

version of the array-based list implementation is not efﬁcient.

Assume that there are n elements in the queue. By analogy to the array-based

list implementation, we could require that all elements of the queue be stored in the

**Linked Queues:-)**

Is like a queue in the Mensa, but professors are allowed to go to

the head of the queue (not passing other professors though)

♦ The element with highest priority (as given by the < relation) is the ﬁrst

one out

♦ If there are elements with equal priority, the ﬁrst one in the queue is

the ﬁrst one out

♦ There are a number of possible implementations, look at a data

structure book for details