Linked List search

Philip Harris

So I have been making progress and have been trying to infuse articles with my old book I am reading about algorithms

so algorithm 2.7 is a linked search I posted it below .....NOTE (UNIFORM() is suppose to be a random number selector from 1 to n)

=========================================================

HERE IS WHERE I AM AT
// I used the list array for loop to print out the linked list to ck myself

using System;

using System.Collections.Generic;

using System.Text;

namespace TreeSort

{

class program

{

static void Main()

{

int[] _list = { 1, 3, 7, 9, 11 };

int n = 12;

int head = 0;

int next = 2;

int x = 12;

LinkedList list = new LinkedList(_list);

list.AddFirst(head);

LinkedListNode first = list.First;

list.AddAfter(first, next);

list.AddLast(n);

int[] ListArray = new int[list.Count];

list.CopyTo(ListArray, 0);

int geuss = list.Count;

foreach (int y in ListArray)

{

Console.WriteLine(y);

}

for (int i = head; i < n; i++)

{

}

Console.ReadKey();

}

3 Replies

Know the answer? Post it — somebody with the same question will find it here.

Vulpes11y ago
Accepted answer
It's not straightforward to express this algorithm in C# because the .NET Framework's LinkedList class is a doubly linked list, not a singly linked list, and it doesn't enable you to access elements by index which is what's needed here.

I think the best thing to do therefore is to write your own 'bare bones' SinglyLinkedList class and provide it with an indexer so that elements can be accessed by index. This isn't too difficult and so I've done it below.

I've also simplified the method parameters as n, head and next can all be deduced from the SinglyLinkedList itself and so can therefore be omitted from the parameter list.

Finally, we have the usual problem with these algorithms that .NET collections are zero based rather than 1-based and so adjustments need to be made for that:

using System;

namespace TreeSort
{
public class Node
{
public Node Next { get;set; }
public T Value { get; set; }
}

public class SinglyLinkedList
{
int count = 0;
public int Count { get{ return count; } }

public Node First { get;set;}

public Node Last
{
get
{
Node current = First;
if (current == null) return null;

while(current.Next != null)
{
current = current.Next;
}

return current;
}
}

public void Append(T value)
{
if (First == null)
{
First = new Node();
First.Value = value;
First.Next = null;
}
else
{
Node last = Last;
Node latest = new Node();
latest.Value = value;
latest.Next = null;
last.Next = latest;
}

count++;
}

public Node this[int index]
{
get
{
if (index < 0 || index >= count)
throw new ArgumentException("Index is out of range");
int counter = 0;
Node current = First;

while (index > counter)
{
current = current.Next;
counter++;
}

return current;
}
}
}
class Program
{
static Random rand = new Random();

static void Main()
{
int[] _list = { 0, 1, 2, 3, 7, 9, 11, 12 };
SinglyLinkedList list = new SinglyLinkedList();

foreach(int i in _list) list.Append(i);

for(int X = 0; X <= 12; X++)
{
int index = LinkedListSearch(list, 4, X);

if (index > 0)
{
Console.WriteLine("{0} was found in the list at index {1}", X, index);
}
else
{
Console.WriteLine("{0} is not in the list", X);
}
}

Console.ReadKey();
}

static int LinkedListSearch(SinglyLinkedList list, int guesses, int X)
{
if (list == null || list.Count == 0) throw new ArgumentException("linked list can't be null or empty");
if (guesses < 1) throw new ArgumentException("guesses must be greater than 0");

int n = list.Count;
int largest = list.First.Value;
int index = 0;

for(int i = 0; i < guesses; i++)
{
int j = rand.Next(0, n); // includes 0, excludes n
if (X > list[j].Value && list[j].Value > list[index].Value)
{
largest = list[j].Value;
index = j;
}
}

while(list[index].Next != null && X > list[index].Value)
{
index++;
}

if(list[index].Value == X)
{
return index + 1; // 1-based return value
}
else
{
return 0;
}
}
}
}

The output is:

0 was found in the list at index 1
1 was found in the list at index 2
2 was found in the list at index 3
3 was found in the list at index 4
4 is not in the list
5 is not in the list
6 is not in the list
7 was found in the list at index 5
8 is not in the list
9 was found in the list at index 6
10 is not in the list
11 was found in the list at index 7
12 was found in the list at index 8
Vulpes11y ago
Although there's nothing you can do about LinkedList being doubly-linked (apart from ignoring the backward linking members) you could use an extension method (say GetItem) to give it indexer functionality.

Here's essentially the program you started writing on that basis i.e. without using a custom SinglyLinkedList class but using instead a GetItem extension method to the existing LinkedList class:

using System;
using System.Collections.Generic;

namespace TreeSort
{
public static class LinkedListExtensions
{
public static LinkedListNode GetItem(this LinkedList list, int index)
{
if (index < 0 || index >= list.Count)
throw new ArgumentException("Index is out of range");
int counter = 0;
LinkedListNode current = list.First;

while (index > counter)
{
current = current.Next;
counter++;
}

return current;
}
}

class Program
{
static Random rand = new Random();

static void Main()
{
int[] _list = { 1, 3, 7, 9, 11 };
int n = 12;
int head = 0;
int next = 2;
LinkedList list = new LinkedList(_list);
list.AddFirst(head);
LinkedListNode second = list.First.Next;
list.AddAfter(second, next); // adding after second node to keep list sorted
list.AddLast(n);
Console.WriteLine("Linked list now contains : ");
for(int i = 0; i < list.Count; i++) Console.Write("{0} ", list.GetItem(i).Value);
Console.WriteLine("\n");

for(int X = 0; X <= 12; X++)
{
int index = LinkedListSearch(list, 4, X);

if (index > 0)
{
Console.WriteLine("{0} was found in the list at index {1}", X, index);
}
else
{
Console.WriteLine("{0} is not in the list", X);
}
}

Console.ReadKey();
}

static int LinkedListSearch(LinkedList list, int guesses, int X)
{
if (list == null || list.Count == 0) throw new ArgumentException("linked list can't be null or empty");
if (guesses < 1) throw new ArgumentException("guesses must be greater than 0");

int n = list.Count;
int largest = list.First.Value;
int index = 0;

for(int i = 0; i < guesses; i++)
{
int j = rand.Next(0, n); // includes 0, excludes n
if (X > list.GetItem(j).Value && list.GetItem(j).Value > list.GetItem(index).Value)
{
largest = list.GetItem(j).Value;
index = j;
}
}

while(list.GetItem(index).Next != null && X > list.GetItem(index).Value)
{
index++;
}

if(list.GetItem(index).Value == X)
{
return index + 1; // 1-based return value
}
else
{
return 0;
}
}
}
}

The output now is:

Linked list now contains :
0 1 2 3 7 9 11 12

0 was found in the list at index 1
1 was found in the list at index 2
2 was found in the list at index 3
3 was found in the list at index 4
4 is not in the list
5 is not in the list
6 is not in the list
7 was found in the list at index 5
8 is not in the list
9 was found in the list at index 6
10 is not in the list
11 was found in the list at index 7
12 was found in the list at index 8

Although you could code the LinkedListSearch first, it can be difficult when you're translating pseudo-code to visualize exactly how the equivalent C# code is going to look without having something concrete to work from.

So, personally, I prefer to work the other way around by writing the C# class (or extension method) first but being prepared to alter it if I then find it doesn't quite do what's wanted.
Philip Harris11y ago
I see what you mean as far as the indexing goes I was curious if that could easily be pulled from the linked list I had. Once again you helped me Vulpes I appreciate it very much as always.

When you look at a problem like this where do you start, I start from the top and go straight down but would it be easier to work backwards and code the LinkedListSearch() first?