Реализация двунаправленного/связанного списка на C#
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Реализация двунаправленного/связанного списка на C# - 2012-02-05 00:53:13.530000
|
|
|
ALE}{_Y
Сообщений: 35
Оценки: 0
Присоединился: 2010-02-14 03:23:27.436666
|
Уважаемые форумчане, прошу заценить реализацию двунаправленного списка на C#.
Исходный код:
public sealed class MyLinkedList<T>
{
public void add(T objectData)
{
if (firstElement == null)
{
ListElement<T> newElement = new ListElement<T>(null, null, objectData);
firstElement = newElement;
lastElement = newElement;
currentElement = newElement;
}
else
{
ListElement<T> newElement = new ListElement<T>(lastElement, null, objectData);
lastElement.NextElement = newElement;
lastElement = newElement;
}
nCount++;
}
//Удаление обьекта на заданной позиции из списка
public void delete(int nIndex)
{
if (firstElement == null)
return;
ListElement<T> delElement = firstElement;
int curPos = 0;
do
{
if (curPos == nIndex)
{
if (delElement == firstElement)
{
if (currentElement == firstElement)
this.moveNext();
firstElement = delElement.NextElement;
delElement.NextElement.PrevElement = delElement.PrevElement;
}
else if (delElement == lastElement)
{
if (currentElement == lastElement)
this.moveBack();
lastElement = delElement.PrevElement;
delElement.PrevElement.NextElement = delElement.NextElement;
}
else
{
if (delElement == currentElement)
this.moveBack();
delElement.PrevElement.NextElement = delElement.NextElement;
delElement.NextElement.PrevElement = delElement.PrevElement;
}
delElement = null;
nCount--;
return;
}
curPos++;
}
while ((delElement = delElement.NextElement) != null);
throw new Exception("IndexOutOfRangeException");
}
//Переход на предыдущий элемент
public Boolean moveNext()
{
if (currentElement != lastElement)
{
currentElement = currentElement.NextElement;
return true;
}
else
{
throw new Exception("IndexOutOfRangeException [MoveNext]");
}
}
//Переход на следующий элемент
public Boolean moveBack()
{
if (currentElement != firstElement)
{
currentElement = currentElement.PrevElement;
return true;
}
else
{
throw new Exception("IndexOutOfRangeException [MoveBack]");
}
}
//Установка CurrentElement в начало списка
public void reset()
{
currentElement = firstElement;
}
//Количество элементов списка
private int nCount = 0;
//Первый элемент списка
private ListElement<T> firstElement;
//Последний элемент списка
private ListElement<T> lastElement;
//Текущий элемент списка
private ListElement<T> currentElement;
public ListElement<T> CurrentItem
{
get { return this.currentElement; }
}
public int Count
{
get { return this.nCount; }
}
}
//Класс элемента списка
public sealed class ListElement<T>
{
public ListElement(ListElement<T> prevElement, ListElement<T> nextElement, T someData)
{
this.prevElement = prevElement;
this.nextElement = nextElement;
this.someData = someData;
}
//Предыдущий элемент
private ListElement<T> prevElement;
//Следующий элемент
private ListElement<T> nextElement;
//Данные, которые будет хранить элемент списка
private T someData;
public T Data
{
get { return this.someData; }
}
//Использую модификатор доступа internal, чтобы свойства
//PrevElement и NextElement были доступны только в данной сборке
internal ListElement<T> PrevElement
{
get { return this.prevElement; }
set { this.prevElement = value; }
}
internal ListElement<T> NextElement
{
get { return this.nextElement; }
set { this.nextElement = value; }
}
}
Хочу узнать Ваше мнение по данному коду, так как меня тревожит следующая вещь.
При использовании родимого .NET-овского LinkedList<T> свойства элемента списка LinkedListNode<T>.First.Next и LinkedList<T>.First.Previous являються доступными только для чтения. Так как я не сумел реализовать класс подобным образом, то в приведенном мной коде свойства ListElement<T>.NextElement и ListElement<T>.PrevElement обьявлены с модификатором доступа internal и то этому не будут доступны извне данной сборки.
Надо ли вообще их делать доступными или нет? Обязательно ли их делать доступными или нет? Целью обьявления их как internal было убережение их модификации в коде, который будет использувать данную сборку/библиотеку. Ибо если убрать set { this.Element = value; }, то пропадет возможность их модификации внутри данной сборки: например, в методах MyLinkedList<T>.add() и MyLinkedList<T>.delete().
Нежелательная модификация свойств может выглядеть следующим образом:
MyLinkedList<int> linkedInt = new MyLinkedList<int>();
linkedInt.add(1);
linkedInt.add(2);
linkedInt.add(3);
linkedInt.add(4);
linkedInt.add(5);
linkedInt.moveNext();
linkedInt.moveNext();
//Нежелательная модификация
linkedInt.CurrentItem.NextElement = new ListElement<int>(null, null, 1);
После выполнения последней операции linkedInt.Count будет указывать корректное количество элементов списка (в данном случае 5), но взаимосвязь нарушится и итерацию по элементам списка без ошибок будет выполнить невозможно.
Следующий код выдаст ошибку:
int curPos = 1;
Console.WriteLine(linkedInt.CurrentItem.Data.ToString());
do
{
linkedInt.moveNext();
Console.WriteLine(linkedInt.CurrentItem.Data.ToString());
curPos++;
}
while (curPos < linkedInt.Count);
Ошибка:
Ежели я оставляю поля ListElement<T>.NextElement и ListElement<T>.PrevElement как internal, то такого не происходит - программа работает нормально. Но нет доступа к этим полям извне сборки (а надо ли он вообще???).
Как на Ваш взгляд, можно оставить класс так, как он реализован, или есть какие-то косяки в коде или архитектуре класса?
Заранее благодарю за ответ.
P.S. гуглил исходники двунаправленный списков на C# - поголовно все оставляют поля ListElement<T>.NextElement и ListElement<T>.PrevElement просто public. Но при использовании такого класса некорректным образом можно допустить ошибку, которая была описана выше.
|
|
|
|
|
RE: Реализация двунаправленного/связанного списка на C# - 2012-02-05 17:19:01.426666
|
|
|
Genco
Сообщений: 1662
Оценки: 90
Присоединился: 2007-12-16 23:11:22.003333
|
quote:
Ибо если убрать set { this.Element = value; }, то пропадет возможность их модификации внутри данной сборки: например, в методах MyLinkedList<T>.add() и MyLinkedList<T>.delete().
Стооп. Не, код вполне хорош, только ты не совсем правильно расставил акцент у проблемы. Ограничивать надо не свойства вспомогательного класса, а те методы, которые будут их неправильно вызывать.
Например, попробуй так: ListElement<T> объяви внутри MyLinkedList<T> и выставь ему спецификатор private. Как результат класс списка сможет им пользоваться как захочет, а бяки-буки из внешнего кода не смогут никак.
|
|
|
|
|
RE: Реализация двунаправленного/связанного списка на C# - 2012-02-06 20:58:11.313333
|
|
|
ALE}{_Y
Сообщений: 35
Оценки: 0
Присоединился: 2010-02-14 03:23:27.436666
|
Если обьявляю класс ListElement<T> внутри MyLinkedList<T> и выставляю ему спецификатор private, то получаю ошибку, что доступность типа свойства MyLinkedList<T>.CurrentElement (обьявленное как public) ниже доступности класса MyLinkedList<T>.ListElement<T>. По этому решил оставить так (часть кода удалил чтобы было удобнее читать):
namespace MyLinkedList
{
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
public sealed class MyLinkedList<T>
{
public void add(T objectData)
{
if (firstElement == null)
{
ListElement<T> newElement = new ListElement<T>(null, null, objectData);
firstElement = newElement;
lastElement = newElement;
currentElement = newElement;
}
else
{
ListElement<T> newElement = new ListElement<T>(lastElement, null, objectData);
//Обращаюсь не к свойству, а непосредственно к полю internal ListElement<R>.nextElement
//
lastElement.nextElement = newElement;
lastElement = newElement;
}
nCount++;
}
public void delete(int nIndex)
{
if (firstElement == null)
return;
ListElement<T> delElement = firstElement;
int curPos = 0;
do
{
if (curPos == nIndex)
{
if (delElement == firstElement)
{
if (currentElement == firstElement)
this.moveNext();
firstElement = delElement.NextElement;
delElement.nextElement.prevElement = delElement.PrevElement;
}
else if (delElement == lastElement)
{
if (currentElement == lastElement)
this.moveBack();
lastElement = delElement.PrevElement;
delElement.prevElement.nextElement = delElement.NextElement;
}
else
{
if (delElement == currentElement)
this.moveBack();
delElement.prevElement.nextElement = delElement.NextElement;
delElement.nextElement.prevElement = delElement.PrevElement;
}
delElement = null;
nCount--;
return;
}
curPos++;
}
while ((delElement = delElement.NextElement) != null);
Console.WriteLine("ArgumentOutOfRangeException");
}
public Boolean moveNext()
{
//
}
public Boolean moveBack()
{
//
}
public void reset()
{
//
}
private int nCount = 0;
private ListElement<T> firstElement;
private ListElement<T> lastElement;
private ListElement<T> currentElement;
public ListElement<T> CurrentItem
{
get { return this.currentElement; }
}
public int Count
{
get { return this.nCount; }
}
}
public sealed class ListElement<R>
{
public ListElement(ListElement<R> prevElement, ListElement<R> nextElement, R someData)
{
this.prevElement = prevElement;
this.nextElement = nextElement;
this.someData = someData;
}
internal ListElement<R> prevElement;
internal ListElement<R> nextElement;
private R someData;
public R Data
{
get { return this.someData; }
}
public ListElement<R> PrevElement
{
get { return this.prevElement; }
}
public ListElement<R> NextElement
{
get { return this.nextElement; }
}
}
}
В результате получаю доступ к свойствам ListElement<R>.PrevElement и ListElement<R>.NextElement только для чтения, а поля ListElement<R>.prevElement и ListElement<R>.nextElement доступны только в данной сборке (то-есть я их напрямую могу использовать в классе MyLinkedList<T>).
Я думаю это будет самый удачный вариант.
|
|
|
|
|
RE: Реализация двунаправленного/связанного списка на C# - 2012-02-06 21:03:09.490000
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
internal
|
|
|
|
|
RE: Реализация двунаправленного/связанного списка на C# - 2012-02-06 21:07:06.266666
|
|
|
ALE}{_Y
Сообщений: 35
Оценки: 0
Присоединился: 2010-02-14 03:23:27.436666
|
да-да, он самый
|
|
|
|
|
RE: Реализация двунаправленного/связанного списка на C# - 2012-02-06 21:35:23.193333
|
|
|
Genco
Сообщений: 1662
Оценки: 90
Присоединился: 2007-12-16 23:11:22.003333
|
quote:
то получаю ошибку, что доступность типа свойства MyLinkedList<T>.CurrentElement (обьявленное как public) ниже доступности класса MyLinkedList<T>.ListElement<T>.
CurrentItem? А, ну да - ты же элемент возвращаешь, этот экземпляр внутреннего объекта - элемента списка (который вместе со ссылками). Я бы возвращал только данные по этому элементу, у которых тип T.
Ну а при иной логике у тебя получается самое оптимальное решение с internal, да.
|
|
|
|
|
|
