Doubly-linked list/Definition: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 7: | Line 7: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
Public Class DoubleLinkList(Of T) |
Public Class DoubleLinkList(Of T) |
||
Private m_Head As Node(Of T) |
Private m_Head As Node(Of T) |
||
Private m_Tail As Node(Of T) |
Private m_Tail As Node(Of T) |
||
Public Sub AddHead(ByVal value As T) |
Public Sub AddHead(ByVal value As T) |
||
Dim node As New Node(Of T)(Me, value) |
Dim node As New Node(Of T)(Me, value) |
||
If m_Head Is Nothing Then |
If m_Head Is Nothing Then |
||
m_Head = Node |
m_Head = Node |
||
Line 21: | Line 21: | ||
m_Head = node |
m_Head = node |
||
End If |
End If |
||
End Sub |
End Sub |
||
Public Sub AddTail(ByVal value As T) |
Public Sub AddTail(ByVal value As T) |
||
Dim node As New Node(Of T)(Me, value) |
Dim node As New Node(Of T)(Me, value) |
||
If m_Tail Is Nothing Then |
If m_Tail Is Nothing Then |
||
m_Head = node |
m_Head = node |
||
Line 35: | Line 35: | ||
End If |
End If |
||
End Sub |
End Sub |
||
Public ReadOnly Property Head() As Node(Of T) |
Public ReadOnly Property Head() As Node(Of T) |
||
Get |
Get |
||
Line 41: | Line 41: | ||
End Get |
End Get |
||
End Property |
End Property |
||
Public ReadOnly Property Tail() As Node(Of T) |
Public ReadOnly Property Tail() As Node(Of T) |
||
Get |
Get |
||
Line 47: | Line 47: | ||
End Get |
End Get |
||
End Property |
End Property |
||
Public Sub RemoveTail() |
Public Sub RemoveTail() |
||
If m_Tail Is Nothing Then Return |
If m_Tail Is Nothing Then Return |
||
If m_Tail.Previous Is Nothing Then 'empty |
If m_Tail.Previous Is Nothing Then 'empty |
||
m_Head = Nothing |
m_Head = Nothing |
||
Line 59: | Line 59: | ||
End If |
End If |
||
End Sub |
End Sub |
||
Public Sub RemoveHead() |
Public Sub RemoveHead() |
||
If m_Head Is Nothing Then Return |
If m_Head Is Nothing Then Return |
||
If m_Head.Next Is Nothing Then 'empty |
If m_Head.Next Is Nothing Then 'empty |
||
m_Head = Nothing |
m_Head = Nothing |
||
Line 71: | Line 71: | ||
End If |
End If |
||
End Sub |
End Sub |
||
End Class |
End Class |
||
Public Class Node(Of T) |
Public Class Node(Of T) |
||
Private ReadOnly m_Value As T |
Private ReadOnly m_Value As T |
||
Private m_Next As Node(Of T) |
Private m_Next As Node(Of T) |
||
Private m_Previous As Node(Of T) |
Private m_Previous As Node(Of T) |
||
Private ReadOnly m_Parent As DoubleLinkList(Of T) |
Private ReadOnly m_Parent As DoubleLinkList(Of T) |
||
Public Sub New(ByVal parent As DoubleLinkList(Of T), ByVal value As T) |
Public Sub New(ByVal parent As DoubleLinkList(Of T), ByVal value As T) |
||
m_Parent = parent |
m_Parent = parent |
||
m_Value = value |
m_Value = value |
||
End Sub |
End Sub |
||
Public Property [Next]() As Node(Of T) |
Public Property [Next]() As Node(Of T) |
||
Get |
Get |
||
Line 92: | Line 93: | ||
End Set |
End Set |
||
End Property |
End Property |
||
Public Property Previous() As Node(Of T) |
Public Property Previous() As Node(Of T) |
||
Get |
Get |
||
Line 100: | Line 102: | ||
End Set |
End Set |
||
End Property |
End Property |
||
Public ReadOnly Property Value() As T |
Public ReadOnly Property Value() As T |
||
Get |
Get |
||
Line 105: | Line 108: | ||
End Get |
End Get |
||
End Property |
End Property |
||
Public Sub InsertAfter(ByVal value As T) |
Public Sub InsertAfter(ByVal value As T) |
||
If m_Next Is Nothing Then |
If m_Next Is Nothing Then |
||
Line 119: | Line 123: | ||
End If |
End If |
||
End Sub |
End Sub |
||
Public Sub Remove() |
Public Sub Remove() |
||
If m_Next Is Nothing Then |
If m_Next Is Nothing Then |
||
Line 129: | Line 134: | ||
End If |
End If |
||
End Sub |
End Sub |
||
End Class |
End Class |
Revision as of 06:20, 25 December 2008
Doubly-linked list/Definition
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
Define the data structure for a complete doubly-linked list.
- The structure should support adding elements to the head, tail and middle of the list.
- The structure should not allow circular loops
Visual Basic .NET
Public Class DoubleLinkList(Of T) Private m_Head As Node(Of T) Private m_Tail As Node(Of T) Public Sub AddHead(ByVal value As T) Dim node As New Node(Of T)(Me, value) If m_Head Is Nothing Then m_Head = Node m_Tail = m_Head Else node.Next = m_Head m_Head = node End If End Sub Public Sub AddTail(ByVal value As T) Dim node As New Node(Of T)(Me, value) If m_Tail Is Nothing Then m_Head = node m_Tail = m_Head Else node.Previous = m_Tail m_Tail = node End If End Sub Public ReadOnly Property Head() As Node(Of T) Get Return m_Head End Get End Property Public ReadOnly Property Tail() As Node(Of T) Get Return m_Tail End Get End Property Public Sub RemoveTail() If m_Tail Is Nothing Then Return If m_Tail.Previous Is Nothing Then 'empty m_Head = Nothing m_Tail = Nothing Else m_Tail = m_Tail.Previous m_Tail.Next = Nothing End If End Sub Public Sub RemoveHead() If m_Head Is Nothing Then Return If m_Head.Next Is Nothing Then 'empty m_Head = Nothing m_Tail = Nothing Else m_Head = m_Head.Next m_Head.Previous = Nothing End If End Sub End Class Public Class Node(Of T) Private ReadOnly m_Value As T Private m_Next As Node(Of T) Private m_Previous As Node(Of T) Private ReadOnly m_Parent As DoubleLinkList(Of T) Public Sub New(ByVal parent As DoubleLinkList(Of T), ByVal value As T) m_Parent = parent m_Value = value End Sub Public Property [Next]() As Node(Of T) Get Return m_Next End Get Friend Set(ByVal value As Node(Of T)) m_Next = value End Set End Property Public Property Previous() As Node(Of T) Get Return m_Previous End Get Friend Set(ByVal value As Node(Of T)) m_Previous = value End Set End Property Public ReadOnly Property Value() As T Get Return m_Value End Get End Property Public Sub InsertAfter(ByVal value As T) If m_Next Is Nothing Then m_Parent.AddTail(value) ElseIf m_Previous Is Nothing Then m_Parent.AddHead(value) Else Dim node As New Node(Of T)(m_Parent, value) Dim temp = m_Next Me.Next = node node.Previous = Me node.Next = temp temp.Previous = node End If End Sub Public Sub Remove() If m_Next Is Nothing Then m_Parent.RemoveTail() ElseIf m_Previous Is Nothing Then m_Parent.RemoveHead() Else m_Previous.Next = Me.Next m_Next.Previous = Me.Previous End If End Sub End Class