Linked-List & Self-Referential Class

Self-Referential Class

Et emne som vi ofte bruger til at implimentere vores ADT´er (Abstract Data Type) er Self-Referential Class og Linked-List er et godt sted at begynde, fordi det kan være svært at håndtere typer som peger på sig selv. Vi bruger denne teknik i Træer og Grafer også.

Lad os kikke lidt nærmere på Self-Referential typer.

En Klasse (C#) som har en reference til samme type.

Class Node

{

Node Next;

}

Forklaring: Det er ikke meget kode, men ret abstrakt. Koden ovenover siger faktisk, at har vi et objekt af typen Node, så kan det have en reference til et anden objekt af samme type, eller til sig selv.

Eksempel 1: To objekter af samme type, hvor et af objekterne reffererer til det andet:

C# kode

Object Diagram

Node a = new Node();

Node b = new Node();

a.Next = b;

Eksempel 2: Et objekt af typen Node som reffererer til sig selv.

C# kode

Object Diagram

Node a = new Node();

a.Next = a;

Linked-List

Nu har du kendskab til den måde man sætter objekter af samme type sammen, så er det ikke langt til Linked-List, som bare er en uendelig lang liste af self-refferenting objects.

For at gøre det praktisk, laver vi ofte en klasse(List) som har listen(samlingen af Node). Og den eneste reference som List har er en Node start. Hele listen hænger således i denne start reference .

Prøv at undersøg Billedet med tilhørende kode, og se om du forstår sammenhænge. Bagefter kan vi udvide List klassen med metoder som arbejder på Listen. Vi skal helst kunne indsætte nye Node´s i listen og hent fra den også, og flere andre ting.

Billede 1:

Kode til Billede 1

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Linked_list

{

class Program

{

static void Main(string[] args)

{

List minList = new List();

}

class List

{

public Node start;

public List()

{

Node n1 = new Node();

Node n2 = new Node();

Node n3 = new Node();

n1.tal = 4;

n2.tal = 2;

n3.tal = 7;

start = n1;

n1.next = n2;

n2.next = n3;

Console.WriteLine(start.tal);

Console.WriteLine(start.next.tal);

Console.WriteLine(start.next.next.tal);

}

class Node

{

public Node next;

public int tal;

}

Add metoden

En af de vigtigste metoder List skal have er Add metoden, ellers kan listen ikke vokse. Det er en god metode at kikke på fordi den viser hvordan man arbejder med en linked-list på en overskuelig måde. Undersøg billedet nedenfor her:

Billede 2:

Kode til Billede 2

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Linked_list

{

class Program

{

static void Main(string[] args)

{

List minList = new List();

minList.add(1);

minList.add(2);

minList.add(3);

minList.printAll();

}

class List

{

public Node start;

public void add(int tal)

{

Node n = new Node();

n.tal = tal;

n.next = start;

start = n;

}

public void printAll()

{

Node iterator = start;

while (iterator != null)

{

Console.WriteLine(iterator.tal);

iterator = iterator.next;

}

class Node

{

public Node next;

public int tal;

}

Læg mærke til at vi nu har tilføjet en Add metode og ikke bruger "manuel" sammensætning af Node objekter. Denne nye metode er en viderudvikling af billede 1, og nu har vi flyttet alt ned i List klassen. Læg mærke til at når vi oppe i Main metoden KUN arbejder med List objektet og har intet node objekt.

Billed 1 eksemplet var primært for at lære fidusen med objekter som hænger sammen. Billede 2 er en mere realistisk software løsning hvor alt indkapsles i én klasse. En yderligere udvikling kunne være at Node klassen blev private for List klassen, således at vi ikke fik lov til at bruge Node klassen i Main, således ville indkapslingen være komplet.

Fagudtryk(Linked-List)

Struct	Struct er kort for Structure. Det ligner en Klasse. Men kan kun holde value typer.De har metoder og værdier, og tilgårs med (.) operatoren.
Simple type	Alle simpel typer: int, bool, char,float....er Value type.
Value type	Er implimenterede som Struct s.
Reference type	Refererer til et objekt i programmet. Er altid null ved initialiseringen.
Boxing conversion	Convertere simple typer til object type. Eks 1. int i = 5; object o = (object) i; Eks 2. object o = i; Unboxing: Eks 1. int i = (int) o;
Self-Referential Class	Et objekt som har en reference til et andet objekt af samme type. Eks. Class Node { Node Next; } Meget centralt med Linked-List, Stacks, Queues og andre data strukturer.
Linked-List	* En linier/sequence samling af selv-refererende objekter ofte kaldt Noder. Disse noder kan holde simple typer eller objekter. Linked list er grund ideen bag de fleste ADS (Abstrakte Data Strukturer).
Circular Linked-List	Identisk med en Linked-List, bare med en reference fra sidste element til første.
Doubly Linked-List	Identisk med en Linked-List, bare med en reference fra hver node til forige node også.