AlgorithmsAndDataStructures/DoublyLinkedList.java at master · biprade/AlgorithmsAndDataStructures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

public class DoublyLinkedList {
private DoublyLinkedList previousNode;
private DoublyLinkedList nextNode;
private int data;

public DoublyLinkedList getPreviousNode() {
	return previousNode;
}
public void setPreviousNode(DoublyLinkedList previousNode) {
	this.previousNode = previousNode;
}
public DoublyLinkedList getNextNode() {
	return nextNode;
}
public void setNextNode(DoublyLinkedList nextNode) {
	this.nextNode = nextNode;
}
public int getData() {
	return data;
}
public void setData(int data) {
	this.data = data;
}
public static int sizeOfLinkedList(DoublyLinkedList headNode)
{
	int count=0;
	if (headNode==null)
		return 0;
	else
	{
		count=1;
		while(headNode.getNextNode()!=null)
		{
			count++;
			headNode=headNode.getNextNode();
		}
	return count;
}

}
public static int insertElement(DoublyLinkedList newNode,int position,DoublyLinkedList headNode)
{
	int size=sizeOfLinkedList(headNode);
	if(headNode==null)
		return -1;
	if (position > size+1 || position < 1)
	{
		System.out.println("Invalid position. Valid position are in the range of 1 to "+(size+1));
		return -1;
	}
	else if (position==1)
	{
		newNode.setNextNode(headNode);
		newNode.setPreviousNode(null);
		headNode.setPreviousNode(newNode);
		return position;

	}
	else
	{
		int count=1;
		DoublyLinkedList previousNode=headNode;
		while (count!=position-1)
		{
			previousNode=previousNode.getNextNode();
			count++;
		}

		DoublyLinkedList nextNode=previousNode.getNextNode();


		previousNode.setNextNode(newNode);
		newNode.setPreviousNode(previousNode);
		newNode.setNextNode(nextNode);
		if (nextNode!=null)
			nextNode.setPreviousNode(newNode);

		return position;
	}
}

public static DoublyLinkedList deleteNode(int position,DoublyLinkedList headNode)
{
	int size=sizeOfLinkedList(headNode);
	if(position < 1 || position > size)
	{
		System.out.println("Invalid position enterd. Valid positions are from 1 to "+size);
		return null;
	}
	if(position==1)
	{
		DoublyLinkedList newHeadNode=headNode.getNextNode();
		newHeadNode.setPreviousNode(null);
		headNode=null;
		System.gc();
		return newHeadNode;
	}
	else
	{
		int count=1;
		DoublyLinkedList previousNode=headNode;
		while(count!=position-1)
		{
			previousNode=previousNode.getNextNode();
			count++;
		}


		DoublyLinkedList newNextNode=previousNode.getNextNode().getNextNode();
		previousNode.setNextNode(newNextNode);
		if(newNextNode!=null)
			newNextNode.setPreviousNode(previousNode);
		return headNode;

	}
}
public static void deleteDoublyLinkedList(DoublyLinkedList headNode)
{
	DoublyLinkedList iterator=headNode;
	DoublyLinkedList temporaryNode;
	while(iterator!=null)
	{
		temporaryNode=iterator;
		iterator=null;

		iterator=temporaryNode.getNextNode();
	}

}
public static void displayList(DoublyLinkedList headNode)
{
DoublyLinkedList currentNode=headNode;
while(currentNode.getNextNode()!=null)
{
	System.out.print(currentNode.getData() + "---->");


	currentNode=currentNode.getNextNode();
}
System.out.println(currentNode.getData());
}

}