Doubly-linked list/Definition: Difference between revisions
Content added Content deleted
(New page: {{task|Data Structures}} Define the data structure for a complete doubly-linked list. * The structure should support adding elements to the head, tail and middle o...) |
No edit summary |
||
Line 4: | Line 4: | ||
* The structure should support adding elements to the head, tail and middle of the list. |
* The structure should support adding elements to the head, tail and middle of the list. |
||
* The structure should not allow circular loops |
* The structure should not allow circular loops |
||
=={{header|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 |
Revision as of 06:19, 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