Elementary Data Structures

Here we examine representat'n of dynamic sets with simple data str tht use pointers.althou vth pointers v can generate complex data str,but v focus on simple str viz. stacks ,queues ,linked lists ,trees .v also c here how objcts n pointers can b synthesised frm arrays.

WOrK In PRoGrEss

stacks

  1. Stacks implement "last in first out"(LIFO) policy.
  2. Here insertion called PUSH n delet'n POP
  3. We can implement Stack at most N-times vth an array of size N.
  4. Here both insert'n n delet'n go by order O(1)
0 21 -2 87 22 14 nill nill

Pseudocodes…

STACK-EMPTY(S)

  1. if Top[S] = 0
  2. then return TRUE
  3. else return FALSE

PUSH(S,x)

  1. if(Top[S] = N)
  2. then error "overflow"
  3. else
  4. Top[S] = Top[S] + 1
  5. S(Top[S]) = x

POP(S)

  1. if(Top[S] = 0)
  2. then error "underflow"
  3. else
  4. Top[S] = Top[S] - 1
  5. return S(Top[S] + 1)

queues

  1. Stacks implement "first in first out"(FIFO) policy.
  2. Here insertion called ENQUEUE n delet'n DEQUEUE
  3. We can implement Queue at most N-times vth an array of size N.
  4. Here both insert'n n delet'n go by order O(1)
nill nill -2 87 22 14 nill nill

Linked Lists

A doubly linked list L has it's each element as an obj with a key or value then two pointers prev n next.prev points 2 previous element in the list next to the next element.c blow


**srry ignore part in b/w this lines thr s problem vth presentation…..

/ 1 -> <_ 0 -> <_ 20 -> <_ __ 3 /

pointers or shown by arrows(thou thy r nt vry clr,I guess u can undrstnd ;) )


A list may have one of several forms. It may be either singly linked or doubly linked, it may
be sorted or not, and it may be circular or not. If a list is singly linked, we omit the prev
pointer in each element. If a list is sorted, the linear order of the list corresponds to the linear
order of keys stored in elements of the list; the minimum element is the head of the list, and
the maximum element is the tail. If the list is unsorted, the elements can appear in any order.
In a circular list, the prev pointer of the head of the list points to the tail, and the next pointer
of the tail of the list points to the head. The list may thus be viewed as a ring of elements.

othr features

  1. Insert'n takes O(1) time, Search takes Theta(N) time …Delet'n if directly the elemnt is given takes O(1) time if jus it's value or key is given as v need 2 do srch 4 tht key it takes Theta(N) time.

psuedocodes…..

LIST-SEARCH(L , k)

  1. x = head[L]
  2. while x != NULL key[x] != k
  3. x = next[x]
  4. return x

LIST-INSERT(L , x)

  1. next[x] = head[L]
  2. prev[x] = NULL
  3. if head[L] != NULL {
  4. prev[head[L]] = x }
  5. head[L] = x
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.