|
Dit artikel is gepubliceerd op zondag 31 juli 2011 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.
22.9.1. LinkedList OpstellenVolgende gedemonstreerde types ( "linked lists" en "trees" ) zijn "graph" types, die bestaan uit verschillend "nodes" ( ook wel "schakels" of "vertices" genoemd ) en die met "edges" met elkaar verbonden zijn.
Het voordeel van graphtypes is dat bewerkingen als toevoegen, invoegen en verwijderen van elementen ( schakels ) sneller kan gaan dan in de meeste andere elementaire collectiestructuren, dit doordat men erg gemakkelijk door de schakels kan gaan navigeren ( "easy traversal" ), en een schakel enkel zijn opvolger en/of zijn voorganger kent. Nadeel is dat men doorgaans niet over indexering beschikt. En dus ook de vormen van "access" naar de elementen beperkt zijn.
In dit voorbeeld is een gelinkte lijst gemaakt van schakels met een Object value, de gelinkte lijst kent zijn begin ( ook wel "head" genoemd ), ieder schakel kent bovendien zijn opvolger ( NextNode ). Dus we hebben hier een "enkelvoudig gelinkte lijst". Enkel de laatste schakel ( ook wel "tail" genoemd ) heeft geen opvolger. Visual Basic 2010 Broncode Class Person Private m_Name As String Public Property Name() As String Get Name = m_Name End Get Set( ByVal value As String) m_Name = value End Set End Property Public Overrides Function ToString() As String ToString = Name End FunctionEnd ClassClass LinkedList Public Class Node Private m_NextNode As Node Private m_Value As Object Public Sub New( ByVal value As Object) Me.Value = value End Sub Public Property NextNode() As Node Get NextNode = m_NextNode End Get Set( ByVal value As Node) m_NextNode = value End Set End Property Public Property Value() As Object Get Value = m_Value End Get Set( ByVal value As Object) m_Value = value End Set End Property End Class Private m_Head As Node Public Property Head() As Node Get Head = m_Head End Get Set( ByVal value As Node) m_Head = value End Set End Property Public ReadOnly Property Count() As Integer Get Dim pointer As Node = Head Do Until pointer Is Nothing Count += 1 pointer = pointer.NextNode Loop End Get End Property Public Sub Add( ByVal node As Node) If Head Is Nothing Then Head = node Else Dim pointer As Node = Head Do Until pointer.NextNode Is Nothing pointer = pointer.NextNode Loop pointer.NextNode = node End If End Sub Public Sub Insert( ByVal node As Node, ByVal beforeNode As Node) Dim previousNode As Node = getPreviousNode(beforeNode) If previousNode IsNot Nothing Then node.NextNode = previousNode.NextNode previousNode.NextNode = node Else If beforeNode Is Head Then node.NextNode = Head Head = node End If End If End Sub Private Function getPreviousNode( ByVal node As Node) As Node Dim pointer As Node = Head Do Until pointer Is Nothing OrElse pointer.NextNode Is node pointer = pointer.NextNode Loop getPreviousNode = pointer End Function Public Sub Remove( ByVal node As Node) Dim previousNode As Node = getPreviousNode(node) If previousNode IsNot Nothing Then previousNode.NextNode = node.NextNode Else If node Is Head Then Head = Head.NextNode End If End If End Sub Public Sub Clear() Head = Nothing End Sub Public Overrides Function ToString() As String Dim pointer As Node = Head Do Until pointer Is Nothing ToString &= pointer.Value.ToString() & " - " pointer = pointer.NextNode Loop End FunctionEnd ClassClass Example Public Shared Sub Main() Dim linkedList1 As LinkedList = New LinkedList PrintLinkedList(linkedList1) Dim node1 As LinkedList. Node = New LinkedList. Node(1) Dim node2 As LinkedList. Node = New LinkedList. Node( New System.Object) Dim node3 As LinkedList. Node = _ New LinkedList. Node( New Person With {.Name = "John Doe"}) linkedList1.Add(node1) linkedList1.Add(node2) linkedList1.Add(node3) PrintLinkedList(linkedList1) linkedList1.Remove(node2) PrintLinkedList(linkedList1) linkedList1.Insert(node2, node1) PrintLinkedList(linkedList1) linkedList1.Clear() PrintLinkedList(linkedList1) Console.ReadLine() End Sub Public Shared Sub PrintLinkedList( ByVal linkedList As LinkedList) Console.WriteLine( "(" & linkedList.Count & ") : " & _ linkedList.ToString()) End SubEnd ClassDownload Visual Basic 2010 Broncode Download Visual C# Sourcecode
Console Application Output (0) :
(3) : 1 - System.Object - John Doe -
(2) : 1 - John Doe -
(3) : System.Object - 1 - John Doe -
(0) : Gelinkte lijsten bestaan in allerlei vormen : met kennis over head en/of tail, enkel of dubbel gelinkt, lineair of cirkelvormig, ...
In sommige variaties maakt men gebruik van een "sentinel" ( "schildwacht" ), dit is een node die geen data ( of "dummy" data ) bevat. Deze is altijd aanwezig en kan gebruikt worden om de implementatie hier en daar te vereenvoudigen, bijvoorbeeld : doordat de sentinel steeds op wacht staat hoeven we nooit de head aan te passen. Nadeel is wel dat deze sentinel natuurlijk wel wat ruimte in beslag neemt, maar doordat gelinkte lijsten toch maar nuttig zijn wanneer er voldoende elementen zijn, is dit nadeel verwaarloosbaar. boven
22.9.2. Typesafe System.Collections.Generic.LinkedList(Of T)Het creëen van eigen linkedlist types kan doorgaans vermeden worden, men kan immers generische instanties van het type LinkedList(Of T) instantiëren.
Voor meer details over dergelijke generieke collectietypes en typesafe collecties, zie de desbetreffende topics.
Dit artikel is gepubliceerd op zondag 31 juli 2011 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.
|