Topics covered:

  • Lists
    • Static and Linked Implementation
    • List<T> and LinkedList<T>
  • Stacks
    • Static and Linked Implementation
    • The Stack<T> Class
  • Queues
    • Circular and Linked Implementation
    • The Queue<T> Class

Video (in Bulgarian)

Presentation Content

The List ADT

  • What is "list"?
    • A data structure (container) that contains a sequence of elements
      • Can have variable size
      • Elements are arranged linearly, in sequence
    • Can be implemented in several ways
      • Statically (using array → fixed size)
      • Dynamically (linked implementation)
      • Using resizable array (the List<T> class)

Static List

  • Implemented by an array
    • Provides direct access by index
    • Has fixed capacity
    • Insertion, deletion and resizing are slow operations

Linked List

  • Dynamic (pointer-based) implementation
  • Different forms
    • Singly-linked and doubly-linked
    • Sorted and unsorted
  • Singly-linked list
    • Each item has 2 fields: value and next
  • Doubly-linked List
    • Each item has 3 fields: value, next and prev

The List<T> Class

  • Implements the abstract data structure list using an array
    • All elements are of the same type T
    • T can be any type, e.g. List<int>, List<string>, List<DateTime>
    • Size is dynamically increased as needed
  • Basic functionality:
    • Count – returns the number of elements
    • Add(T) – appends given element at the end

List<T> – Simple Example

List<string> list = new List<string>() { "C#", "Java" };
list.Add("SQL");
list.Add("Python");
foreach (string item in list)
{
Console.WriteLine(item);
}
// Result: // C# // Java // SQL // Python

List<T> – Functionality

  • list[index] – access element by index
  • Insert(index, T) – inserts given element to the list at a specified position
  • Remove(T) – removes the first occurrence of given element
  • RemoveAt(index) – removes the element at the specified position
  • Clear() – removes all elements
  • Contains(T) – determines whether an element is part of the list
  • IndexOf() – returns the index of the first occurrence of a value in the list (zero-based)
  • Reverse() – reverses the order of the elements in the list or a portion of it
  • Sort() – sorts the elements in the list or a portion of it
  • ToArray() – converts the elements of the list to an array
  • TrimExcess() – sets the capacity to the actual number of elements

List<T>: How It Works?

  • List<T> keeps a buffer memory, allocated in advance, to allow fast Add(T)
    • Most operations use the buffer memory and do not allocate new objects
    • Occasionally the capacity grows (doubles)

Primes in an Interval – Example

static List<int> FindPrimes(int start, int end)
{
List<int> primesList = new List<int>();
for (int num = start; num <= end; num++)
{
bool prime = true;
for (int div = 2; div <= Math.Sqrt(num); div++)
{
if (num % div == 0)
{
prime = false; break;
}
}
if (prime)
{
primesList.Add(num);
}
}
return primesList;
}

Union and Intersection – Example

int[] Union(int[] firstArr, int[] secondArr)
{
List<int> union = new List<int>();
union.AddRange(firstArray);
foreach (int item in secondArray)
if (! union.Contains(item))
union.Add(item);
return union.ToArray();
}

int
[] Intersection(int[] firstArr, int[] secondArr)
{
List<int> intersect = new List<int>();
foreach (int item in firstArray)
if (Array.IndexOf(secondArray, item) != -1)
intersect.Add(item);
return intersect.ToArray();
}

The LinkedList<T> Class

  • Implements the abstract data structure list using a doubly-linked dynamic structure
    • All elements are of the same type T
    • T can be any type, e.g. LinkedList<int>, LinkedList<string>, etc.
    • Elements can be added at both sides
  • Basic LinkedList<T> functionality:
    • AddFirst(T), AddLast(T), AddBefore(T), AddAfter(T), RemoveFirst(T), RemoveLast(T), Count

LinkedList<T> – Example

LinkedList<string> list = new LinkedList<string>();
list.AddFirst("First");
list.AddLast("Last");
list.AddAfter(list.First, "After First");
list.AddBefore(list.Last, "Before Last");
Console.WriteLine(String.Join(", ", list));
// Result: First, After First, Before Last, Last }

Sorting Lists

List<DateTime> list = new List<DateTime>()
{
new DateTime(2013, 4, 7),
new DateTime(2002, 3, 12),
new DateTime(2012, 1, 4),
new DateTime(1980, 11, 11)
};
list.Sort();
list.Sort((d1, d2) => -d1.Year.CompareTo(d2.Year));
list.OrderBy(date => date.Month)));

The Stack ADT

  • LIFO (Last In First Out) structure
  • Elements inserted (push) at “top”
  • Elements removed (pop) from “top”
  • Useful in many situations
    • E.g. the execution stack of the program
  • Can be implemented in several ways
    • Statically (using array)
    • Dynamically (linked implementation)
    • Using the Stack<T> class

Static Stack

  • Static (array-based) implementation
    • Has limited (fixed) capacity
    • The current index (top) moves left / right with each pop / push

Linked Stack

  • Dynamic (pointer-based) implementation
    • Each item has 2 fields: value and next
    • Special pointer keeps the top element

The Stack<T> Class

  • Implements the stack data structure using an array
    • Elements are from the same type T
    • T can be any type, e.g. Queue<int>
    • Size is dynamically increased as needed
  • Basic functionality:
    • Push(T) – inserts elements to the stack
    • Pop() – removes and returns the top element from the stack
  • Basic functionality:
    • Peek() – returns the top element of the stack without removing it
    • Count – returns the number of elements
    • Clear() – removes all elements
    • Contains(T) – determines whether given element is in the stack
    • ToArray() – converts the stack to an array
    • TrimExcess() – sets the capacity to the actual number of elements

Stack<T> – Example

  • Using Push(), Pop() and Peek() methods
Stack<string> stack = new Stack<string>();
stack.Push("1. Ivan");
stack.Push("2. Nikolay");
stack.Push("3. Maria");
stack.Push("4. George");
Console.WriteLine("Top = {0}", stack.Peek());
while (stack.Count > 0)
{
string personName = stack.Pop();
Console.WriteLine(personName);
}

Matching Brackets – Example

  • We are given an arithmetical expression with brackets that can be nested
  • Goal: extract all sub-expressions in brackets
  • Example:
    • 1 + (2 - (2+3) * 4 / (3+1)) * 5
  • Result:
    • (2+3) | (3+1) | (2-(2+3) * 4 / (3+1))
  • Algorithm:
    • For each ’(’ push its index in a stack
    • For each ’)’ pop the corresponding start index

Matching Brackets – Solution

string expression = "1 + (2 (2+3) * 4 / (3+1)) * 5";
Stack<int> stack = new Stack<int>();
for (int index = 0; index < expression.Length; index++)
{
char ch = expression[index];
if (ch == '(')
{
stack.Push(index);
}
else if (ch == ')')
{
int startIndex = stack.Pop();
int length = index startIndex + 1;
string contents = expression.Substring(startIndex, length);
Console.WriteLine(contents);
}
}

The Queue ADT

  • FIFO (First In First Out) structure
  • Elements inserted at the tail (Enqueue)
  • Elements removed from the head (Dequeue)
  • Useful in many situations
    • Print queues, message queues, etc.
  • Can be implemented in several ways
    • Statically (using array)
    • Dynamically (using pointers)
    • Using the Queue<T> class

Static Queue

  • Static (array-based) implementation
    • Has limited (fixed) capacity
    • Implement as a “circular array”
    • Has head and tail indices, pointing to the head and the tail of the cyclic queue

Linked Queue

  • Dynamic (pointer-based) implementation
    • Each item has 2 fields: value and next
    • Dynamically create and delete objects

The Queue<T> Class

  • Implements the queue data structure using a circular resizable array
    • Elements are from the same type T
    • T can be any type, e.g. Queue<int>
    • Size is dynamically increased as needed
  • Basic functionality:
    • Enqueue(T) – adds an element to theend of the queue
    • Dequeue() – removes and returns the element at the beginning of the queue
  • Basic functionality:
    • Peek() – returns the element at the beginning of the queue without removing it
    • Count – returns the number of elements
    • Clear() – removes all elements
    • Contains(T) – determines whether given element is in the queue
    • ToArray() – converts the queue to an array
    • TrimExcess() – sets the capacity to the actual number of elements in the queue

Queue<T> – Example

  • Using Enqueue() and Dequeue() methods
Queue<string> queue = new Queue<string>();
queue.Enqueue("Message One");
queue.Enqueue("Message Two");
queue.Enqueue("Message Three");
queue.Enqueue("Message Four");
while (queue.Count > 0)
{
string message = queue.Dequeue();
Console.WriteLine(message);
}

Sequence N, N+1, 2*N

  • We are given the sequence:
  • Find the first index of given number P
  • Example: N = 3, P = 16
    • S = 3, 4, 6, 5, 8, 7, 12, 6, 10, 9, 16, 8, 14, …
    • Index of P = 11

Sequence – Solution with a Queue

int n = 3, p = 16;
Queue<int> queue = new Queue<int>();
queue.Enqueue(n);
int index = 0;
while (queue.Count > 0)
{
int current = queue.Dequeue();
index++;
if (current == p)
{
Console.WriteLine("Index = {0}", index);
return;
}
queue.Enqueue(current+1);
queue.Enqueue(2*current);
}

List Interfaces in .NET

  • IEnumerable, IEnumerable<T>
    • GetEnumerator()Current, MoveNext()
  • ICollection, ICollection<T>
    • Inherits from IEnumerable<T>
    • Count, Add(…), Remove(…), Contains(…)
  • IList, IList<T>
    • Inherits from ICollection<T>
    • Item / indexer [], Insert(…), RemoveAt(…)

Summary

  • The basic linear data structures in the computer programming are:
    • List (static, linked)
      • Implemented by the List<T> and LinkedList<T> classes in .NET
    • Stack (static, linked)
      • Implemented by the Stack<T> class in .NET
    • Queue (static, linked)
      • Implemented by the Queue<T> class in .NET