Doubly Linked Lists in Data Structures
Module 8 - Part 2
Doubly Linked Lists
C
h
a
l
l
e
n
g
e
Write a recursive method that adds 10 to the data in
each node of a linked list.
C
h
a
l
l
e
n
g
e
S
o
l
u
t
i
o
n
Write a recursive method that adds 10 to the data in
each node of a linked list.
void AddTen(Node n)
{if (n != null)
{n.Data += 10;
AddTen(n.Next);
}
}
D
o
u
b
l
y
L
i
n
k
e
d
L
i
s
t
•
Each node has two links: one forward (as before)
and one backward.
•
The
Node
class now has an additional instance
variable:
•
previous
, the previous
Node.
•
Thus, we can traverse a doubly linked list either
forward or backwards.
•
Every time we insert or delete, both links must be
updated.
D
o
u
b
l
y
L
i
n
k
e
d
N
o
d
e
•
A doubly linked node looks like this
•
The right arrow represents
next
.
•
The left arrow represents
previous
.
I
n
s
e
r
t
i
n
g
i
n
a
D
o
u
b
l
y
L
i
n
k
e
d
L
i
s
t
There are three cases:
•
insert at the beginning.
•
insert in the middle.
•
insert at the end.
Updating the links will differ in the three cases above.
Furthermore, when a node is inserted at the beginning,
head
needs to be updated.
I
n
s
e
r
t
i
n
g
i
n
t
h
e
M
i
d
d
l
e
In order to insert a node before a node named
current
,
the following steps need to be performed:
•
Instantiate a new node.
•
Set two forward links: new node to
current
, node
before
current
to new node.
•
Set two backward links:
current
to new node, new
node to node before
current
.
•
Update the number of items.
Updating the links will differ in the three cases above.
I
n
s
e
r
t
i
n
g
i
n
t
o
a
D
o
u
b
l
y
L
i
n
k
e
d
L
i
s
t
1. Instantiate
the
new node
2. Set
next
in
new
node to
current
.
I
n
s
e
r
t
i
n
g
i
n
t
o
a
D
o
u
b
l
y
L
i
n
k
e
d
L
i
s
t
3.
Set
next
in node
before
current
to
the
new node.
4. Set
previous
in
the
new node to the
node
before
current.
I
n
s
e
r
t
i
n
g
i
n
t
o
a
D
o
u
b
l
y
L
i
n
k
e
d
L
i
s
t
5. Set
previous
in
current
to the
new
node.
D
e
l
e
t
i
n
g
f
r
o
m
a
D
o
u
b
l
y
L
i
n
k
e
d
L
i
s
t
There are four cases:
•
delete at the beginning.
•
delete in the middle.
•
delete at the end.
•
cannot delete.
•
Updating the links will differ in the first three cases
above.
•
Furthermore, when a node is deleted at the beginning,
head
needs to be updated.
D
e
l
e
t
i
n
g
i
n
t
h
e
M
i
d
d
l
e
o
f
a
D
o
u
b
l
y
L
i
n
k
e
d
L
i
s
t
We will delete the
Player
with id 7
1.
Set
next
in the node
before
current
to the
node
after
current.
2. Set previous in the
node
after
current
to the
node
before
current
.
C
#
d
o
u
b
l
y
l
i
n
k
e
d
l
i
s
t
N
o
d
e
s
•
The nodes of the linked list are called
LinkedListNodes and are also generic.
•
LinkedListNode<string> myNode = LL1.First;
•
First and Last are properties of the LinkedList class
that allow direct access to the first and last nodes
respectively
.
C
#
d
o
u
b
l
y
l
i
n
k
e
d
l
i
s
t
•
The linked list class in C# is a generic and doubly
linked which means that we have direct access to the
front and the end of the linked list.
LinkedList<string> LL1 = new LinkedList<string>();
LL1.AddFirst("a"); LL1.AddLast("c");T
r
a
v
e
r
s
i
n
g
b
y
N
o
d
e
s
public static void PrintList (LinkedList<string> L)
{LinkedListNode<string> myNode = L.First;
while (myNode != null) {Console.Write(myNode.Value + " ");
myNode = myNode.Next;
}
Console.WriteLine();
}
J
a
v
a
D
o
u
b
l
y
l
i
n
k
e
d
l
i
s
t
LinkedList<String> LL = new LinkedList<String>();
System.out.println(LL);
LL.addFirst("bill"); System.out.println("display1 "+ LL); LL.addFirst("tom"); System.out.println("display2 "+ LL); LL.addLast("joe"); System.out.println("display3 "+ LL); LL.addFirst("art"); System.out.println("display4 "+ LL);LL.removeFirst();
System.out.println("display5 "+ LL);PrintList(LL);
System.out.println("display6 "+ LL);P
r
i
n
t
i
n
g
t
h
e
h
a
r
d
w
a
y
public static void PrintList (LinkedList<String> L)
{LinkedList<String> temp=new LinkedList<String>();
for(String s : L)
temp.addLast(s);
while (temp.size()>0)
{String myData = temp.removeFirst();
System.out.println(myData + " ");
}
System.out.println();
}
Doubly linked lists contain nodes with both forward and backward links, allowing traversal in both directions. The nodes can be inserted or deleted at the beginning, middle, or end, requiring updating of links accordingly. Additionally, a recursive method can be used to manipulate data in each node, such as adding 10 to the data recursively. This summary provides insights into the structure and operations related to doubly linked lists.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Module 8 - Part 2 Doubly Linked Lists
Challenge Write a recursive method that adds 10 to the data in each node of a linked list.
Challenge Solution Write a recursive method that adds 10 to the data in each node of a linked list. void AddTen(Node n) { if (n != null) { n.Data += 10; AddTen(n.Next); } }
Doubly Linked List Each node has two links: one forward (as before) and one backward. The Node class now has an additional instance variable: previous, the previous Node. Thus, we can traverse a doubly linked list either forward or backwards. Every time we insert or delete, both links must be updated.
Doubly Linked Node A doubly linked node looks like this The right arrow represents next. The left arrow represents previous.
Inserting in a Doubly Linked List There are three cases: insert at the beginning. insert in the middle. insert at the end. Updating the links will differ in the three cases above. Furthermore, when a node is inserted at the beginning, head needs to be updated.
Inserting in the Middle In order to insert a node before a node named current, the following steps need to be performed: Instantiate a new node. Set two forward links: new node to current, node before current to new node. Set two backward links: current to new node, new node to node before current. Update the number of items. Updating the links will differ in the three cases above.
Inserting into a Doubly Linked List 1. Instantiate the new node 2. Set next in new node to current.
Inserting into a Doubly Linked List 3. Set next in node before current to the new node. 4. Set previous in the new node to the node before current.
Inserting into a Doubly Linked List 5. Set previous in current to the new node.
Deleting from a Doubly Linked List There are four cases: delete at the beginning. delete in the middle. delete at the end. cannot delete. Updating the links will differ in the first three cases above. Furthermore, when a node is deleted at the beginning, head needs to be updated.
Deleting in the Middle of a Doubly Linked List We will delete the Player with id 7 1. Set next in the node before current to the node after current. 2. Set previous in the node after current to the node before current.
C# doubly linked list Nodes The nodes of the linked list are called LinkedListNodes and are also generic. LinkedListNode<string> myNode = LL1.First; First and Last are properties of the LinkedList class that allow direct access to the first and last nodes respectively.
C# doubly linked list The linked list class in C# is a generic and doubly linked which means that we have direct access to the front and the end of the linked list. LinkedList<string> LL1 = new LinkedList<string>(); LL1.AddFirst("a"); LL1.AddLast("c");
Traversing by Nodes public static void PrintList (LinkedList<string> L) { LinkedListNode<string> myNode = L.First; while (myNode != null) { Console.Write(myNode.Value + " "); myNode = myNode.Next; } Console.WriteLine(); }
Java Doubly linked list LinkedList<String> LL = new LinkedList<String>(); System.out.println(LL); LL.addFirst("bill"); System.out.println("display1 "+ LL); LL.addFirst("tom"); System.out.println("display2 "+ LL); LL.addLast("joe"); System.out.println("display3 "+ LL); LL.addFirst("art"); System.out.println("display4 "+ LL); LL.removeFirst(); System.out.println("display5 "+ LL); PrintList(LL); System.out.println("display6 "+ LL);
Printing the hard way public static void PrintList (LinkedList<String> L) { LinkedList<String> temp=new LinkedList<String>(); for(String s : L) temp.addLast(s); while (temp.size()>0) { String myData = temp.removeFirst(); System.out.println(myData + " "); } System.out.println(); }
