Перед тем как писать метод добавления или удаления элемента из списка следует ясно представлять свойства той операции, которую Вы собираетесь реализовать; область ее действия - те элементы, которые будут изменены во время ее выполнения; количество случаев, которые стоит рассмотреть при написании этой операции.
Возьмем односвязный линейный список.
Конструктор узла первым параметром принимает значение узла, вторым - ссылку на следующий узел.
Операция поиска целевого элемента x
| Code | 1
2
3
4
5
6
7
8
9
10
| current = Head
while (current != null) && (current.Value != x)
{
current = current.Next
}
if (current == null)
{
Error("InvalidArgument")
}
return current |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
| previous = null
current = Head
while (current != null) && (current.Value != x)
{
previous = current
current = current.Next
}
if (current == null)
{
Error("InvalidArgument")
}
return previous |
|
Меняются: Head [всегда], Tail [только, если список был пуст на момент добавления элемента]
| Code | 1
2
3
4
5
6
7
| node = new Node(x, Head)
if (Count == 0)
{
Tail = node
}
Head = node
Count++ |
|
Меняются: Head [только, если список был пуст на момент добавления элемента], Tail [всегда]
| Code | 1
2
3
4
5
6
7
8
9
10
11
| node = new Node(x, null)
if (Count == 0)
{
Head = node
}
else
{
Tail.Next = node
}
Tail = node
Count++ |
|
Меняются: Head [только, если вставка производится перед текущей головой], Tail [никогда]
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
| previous = FindPrevious(y)
if (previous == null)
{
node = new Node(x, Head)
Head = node
}
else
{
node = new Node(x, previous.Next)
previous.Next = node
}
Count++ |
|
Меняются: Head [никогда], Tail [только, если вставка производится после текущего хвоста]
| Code | 1
2
3
4
5
6
7
8
| previous = Find(y)
node = new Node(x, previous.Next)
previous.Next = node
if (previous == Tail)
{
Tail = node
}
Count++ |
|
Меняются: Head [всегда], Tail [только, если в списке остался единственный узел]
| Code | 1
2
3
4
5
6
7
8
9
10
| if (Count == 0)
{
Error("InvalidCount")
}
Head = Head.Next
if (Count == 1)
{
Tail = null
}
Count-- |
|
Меняются: Head [только, если в списке остался единственный узел], Tail [всегда]
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| if (Count == 0)
{
Error("InvalidCount")
}
if (Count == 1)
{
Head = null
Tail = null
}
else
{
previous = Head
while (previous.Next != Tail)
{
previous = previous.Next
}
previous.Next = null
Tail = previous
}
Count-- |
|
Меняются: Head [только, если удаляемый элемент первый], Tail [никогда]
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| if (Count < 2)
{
Error("InvalidCount")
}
if (Head.Next.Value == x)
{
Head = Head.Next
}
else
{
previous = Head
while (previous.Next.Next.Value != x)
{
previous = previous.Next
}
previous.Next = previous.Next.Next
}
Count-- |
|
Меняются: Head [только, если удаляемый элемент первый], Tail [только, если удаляемый элемент последний]
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| if (Count == 0)
{
Error("InvalidCount")
}
if (Head.Value == x)
{
Head = Head.Next
if (Count == 1)
{
Tail = null
}
}
else
{
previous = FindPreviuos(x)
if (previous.Next == Tail)
{
Tail = previous
}
previous.Next = previous.Next.Next
}
Count-- |
|
Операция удаления следующего элемента для элемента со значением x
Меняются: Head [никогда], Tail [только, если удаляемый элемент последний]
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| if (Count < 2)
{
Error("InvalidCount")
}
else
{
previous = Find(x)
if (previos.Next == null)
{
Error("NothingToRemove")
}
if (previous.Next == Tail)
{
Tail = previous
}
previous.Next = previous.Next.Next
}
Count-- |
|
|
