Bakgrund
Generiska klasser, eller generics, är en teknik som erbjuder ytterligare ett verktyg i din verktygslåda. Du har säkert redan stött på generiska klasser redan om du använt t.ex. List<T> eller någon annan dynamisk lagring. Men kan du skriva egna generiska klasser?
I denna artikel ska vi skapa en egen dynamiskt länkad lista med hjälp av generiska klasser. Redan nu vill jag påpeka att du bör undvika att skriva egna lagringsklasser om du inte har väldigt goda skäl till att göra så. Vårt skäl just nu är att vi behöver ett verkligt problem att lösa samtidigt som vi kan lära oss hur länkade listor fungerar.
Typen T
Vi börjar med en klass – Node<T>.
namespace MyLinkedList
{
class Node<T>
{
public Node<T> Next;
public T Value;
public override string ToString()
{
if (Value != null)
return Value.ToString();
else
return "NULL!!!!";
}
}
}
Märk hur vi har deklarerat en okänd typ T i klassnamnet. Detta betyder att när klassen ska skapas så måste vi ange vilken denna typ T verkligen är. Men klassen behöver inte veta det. Den behöver bara använda typen T. Konstigt? Ja, lite!
Typen T används för att lagra ett värde eller en referens av typen T i medlemmen Value (Next kommer att användas längre fram). Det betyder faktiskt att vi redan har en enkel generisk lagringsklass som kan lagra ett värde. Vi passar på att ändra metoden ToString() så att vi returnerar nodens värde eller ”NULL!!” om vi helt saknar värde. Vi kikar på ett enkelt program som använder klassen med lite olika typer:
using System;
namespace MyLinkedList
{
class Program
{
static void Main(string[] args)
{
var node1 = new Node<int>();
node1.Value = 10;
var node2 = new Node<string>();
node2.Value = "some text";
var node3 = new Node<object>();
Console.WriteLine(node1);
Console.WriteLine(node2);
Console.WriteLine(node3);
}
}
}
Som vi kan se så går det nu utmärkt att använda vår klass Node till att lagra både int, string och object och faktiskt alla andra typer vi kan komma på.
Men varför typen T? Jo traditionellt sett så använder man stora enkla bokstäver där just T är en förkortning av type. Faktum är att det bara är ett variabelnamn för en okänd typ. Vi skulle lika gärna kunna skriva typen A eller typen Typ1.
Olika exempel
Innan vi går vidare med att konstruera en fungerande länkad lista så bör vi gå igenom några regler vad det gäller generiska klasser.
- Man kan använda flera typer i en generisk klass. Exempel är t.ex. Dictionary<TKey, TValue> eller Tuple<T1, T2>.
- Man kan deklarera en typ som bara hör till en metod och inte till själva klassen, t.ex. metoden Swap i exemplet nedan.
static void Swap<T>(ref T lhs, ref T rhs)
{
T temp;
temp = lhs;
lhs = rhs;
rhs = temp;
}
public static void TestSwap()
{
int a = 1;
int b = 2;
Swap<int>(ref a, ref b);
System.Console.WriteLine(a + " " + b);
}
- Man kan begränsa typen T som ska användas i den generiska klassen med nyckelordet where. Exempel:
- where T : struct
- where T : class
- where T : basklass
- where T : interface namn
public class GenericList<T> where T : Employee
{
...
}
Länkad lista
Åter till vårt exempel att bygga en länkad lista. Vad är egentligen en länkad lista? Jo, genom att lägga det vi vill lagra i noder så kan vi länka samman noderna till en tänkt kedja där varje nod kan känner till den nod som kommer efter i kedjan (Next).
Det vi behöver nu är en övergripande klass som kan hjälpa oss att lägga till data samt se till att kedjan bildas. Vi behöver klassen MyLinkedList.
namespace MyLinkedList
{
class MyLinkedList<T>
{
public Node<T> First { get; set; }
public void AddFirst(T data)
{
Node<T> newNode = new Node<T>();
newNode.Value = data;
if (First != null)
newNode.Next = First;
First = newNode;
}
}
}
Genom att skapa egenskapen First så kan klassen alltid hålla reda på vilken nod som ligger först i kedjan. Klassen känner faktiskt inte till några andra noder. När sedan AddFirst() anropas så skapas en ny nod av typen T som lagrar den data som skickas med. Den nya noden ”knuffar” undan den föregående (om en sådan finns) men ser samtidigt till att den nya länkas till den gamla via Next.
Nu kan vi faktiskt testa en dynamiskt länkad lista i sin helhet! Genom att plocka ut den första noden via First så kan vi sedan iterera (loop’a) igenom alla (via Next) till dess att vi når slutet då sista noden alltid är null.
En demonstration.
using System;
namespace MyLinkedList
{
class Program
{
static void Main(string[] args)
{
MyLinkedList<int> test = new MyLinkedList<int>();
test.AddFirst(1);
test.AddFirst(2);
test.AddFirst(3);
var node = test.First;
while (node != null)
{
Console.WriteLine(node);
node = node.Next;
}
}
}
}
Länkad lista vs. Lista
Vad är egentligen skillnaden mellan en länkad lista och en ”vanlig” lista?
Jo, en vanlig List<T> har bakom kulisserna ett fält av typen T som lagring. Listan känner till alla element då det i praktiken finns en T lista[antal] deklarerad inuti klassen.
Det finns en rad för- och nackdelar mellan de olika. Den främsta fördelen en länkad lista har är att den mycket snabbt kan skapa en ny nod och länka in i listan på önskad plats. Speciellt snabb är den om man ska lägga något först i listan. En vanlig lista däremot måste skapa om sin interna lista varje gång man gör en infogning i listan (ej i slutet) samt om det statiska utrymmet man har i det interna fältet blir för litet.
En stor fördel med en vanlig lista är att du kan använda en indexerare och direkt nå ett värde i listan, precis som på fält. Visst sa vi att en vanlig lista använder just fält bakom kulisserna?
Faktum är att du som regel alltid bör använda en vanlig lista just för att den är så optimal om du vill plocka ut värden via index.
.NET erbjuder såklart en färdig LinkedList klass redan.
Skapa en indexerare
Nu ska vi i vår klass skapa en indexerare för att enkelt nå våra värden i vår länkad lista. Du kommer nu samtidigt att förstå varför en länkad lista inte alltid är en bra idé.
Indexeraren gör att vi kan använda hakparenteser [] på vår samling, precis som på ett fält. Skillnaden är att vi kontrollerar hur logiken ser ut får att kunna plocka fram värdet på plats index. Det blir inte så optimalt…
using System;
namespace MyLinkedList
{
class MyLinkedList<T>
{
public int Count { get; set; }
public Node<T> First { get; set; }
public void AddFirst(T data)
{
Node<T> newNode = new Node<T>();
newNode.Value = data;
if (First != null)
newNode.Next = First;
First = newNode;
Count++;
}
public T this[int index]
{
get
{
if(index >= Count)
throw new IndexOutOfRangeException();
Node<T> nod = First;
int i = 0;
while (i < index)
{
nod = nod.Next;
i++;
}
return nod.Value;
}
}
}
}
using System;
namespace MyLinkedList
{
class Program
{
static void Main(string[] args)
{
MyLinkedList<int> test = new MyLinkedList<int>();
test.AddFirst(1);
test.AddFirst(2);
test.AddFirst(3);
for (int i = 0; i < test.Count; i++)
{
Console.WriteLine(test[i]);
}
}
}
}
Som du ser så blir det en loop varje gång du söker ett index i den länkade lista. Detta då den länkade listan inte känner till alla element/noder utan måste söka sig fram till ett visst index.
Vi var tvungna att lägga till en kolla på hur många noder/element vi har i listan via Count. När vi har antalet så kunde vi nu också göra en vanlig for-loop för att iterera igenom vår samling.
Avslutning
Fördelarna med generiska klasser är att du kan få tydligare typade klasser. Du kan ha en dynamisk lista som lagrar just int eller string. Utan generiska klasser hade det bara funnits en klass, ArrayList, som bara lagrade object. Det hade såklart fungerat då allt faktiskt är object men samtidigt mycket bökigt att varje gång konvertera ett object till sin rätta typ när du ska använda din data.
Du har nu också möjlighet att göra algoritmer generiska. Som i exemplet ovan med Swap så byter den plats på två värden/referenser. Nu är det möjligt att t.ex. skriva generiska sorteringsalgoritmer som kan sortera allt så länge det är jämförbart (IComparable).
Vår implementation av MyLinkedList har en del brister. Främst att vi exponerar klassen Node samt referenser till själva noderna. En samlingsklass bör vara lite mer ”tålig” och skyddad så att man inte kan ha sönder t.ex. kedjan av noder genom att sätta en nods Next till null.
Det är kanske inte ofta som du som programmerare verkligen behöver skriva generiska klasser. Vi kan dock lova att det kommer situationer där du har nytta av att skriva generiska klasser och där lösningarna blir både elegantare och enklare.
Övningar
Övningarna som följer låter dig bygga vidare på klassen MyLinkedList som presenterats tidigare i artikeln.
Övning 1
Skapa en metod RemoveFirst() som tar bort det första elementet i den länkade listan. Listan ska därefter fortfarande fungera, dvs. First ska peka på det som tidigare var andra noden.Övning 2
Skapa metoderna InsertAt(int index) och RemoveAt(int index). Om inte index passar så ska ett IndexOutOfRangeException kastas. Tänk på att du redan har en indexerare i klassen.Övning 3
Det finns något som kallas för en ”dubbellänkad lista”. Det betyder att varje nod också känner till sin föregående nod. Att man alltså kan via en nod ”stega bakåt” i kedjan.Detta är en egenskap som måste ligga i nod-klassen. Skapa en egenskap som heter Previous i nod-klassen. Se till att länkningen med noderna fungerar vid insättning och borttagning.
Övning 4
Lägg till egenskapen Last i MyLinkedList. Last ska alltid referera till den sista noden i samlingen.Övning 5
Skapa metoderna AddLast(T data) samt RemoveLast(). Nu när du har egenskapen Previous i varje nod så blir det lite lättare.Övning 6
Detta blir en lite större avslutande övning.Skapa en ny klass kallad MyList. Den ska ha samma metoder som MyLinkedList har efter övning 5. Implementera lagringen i MyList med hjälp av fält. Du ska alltså inte använda klassen Node i denna uppgift.
Senaste kommentarer