Вдвойне связанный список LinkedList ремейк в Java


Я учусь программировать на Java, и я решил реализовать двусвязный список как практика и как проект моста прежде, чем идти на изучении c++. Я знаю, что Java включает коллекции LinkedList реализации, но я написал это на практике. У меня есть готовый код и он работает правильно. Однако, я был бы признателен некоторые отзывы о стиль и вещи, которые я должен сделать по-другому или вообще не.

Кроме того, обратите внимание: я не очень беспокоюсь о единого стиля документации; я знаю, что это немного сломан. Я только добавил он из вежливости к людям, которые могут читать мой код. Меня больше интересуют отзывы о мой стиль кодирования.

MyLinkedList

import java.util.NoSuchElementException;

public class MyLinkedList<T> {

protected MyNode<T> firstNode;
protected MyNode<T> lastNode;
protected int size;

/**
 * Constructs a new Linked List
 */
public MyLinkedList() {
    firstNode = new MyNode<T>();
    lastNode = firstNode;
    size = 0;

}

/**
 * Adds an element to the linked list
 * 
 * @param element
 *            to be added to linked list
 */
public void add(T content) {
    if (size == 0)
        firstNode.setContent(content);
    else
        lastNode = lastNode.spawnNode(content);
    size++;
}

/**
 * Adds an element to the beginning of the linked list
 * 
 * @param content
 *            element to be added to linked list
 */
public void addFirst(T content) {
    if (size == 0)
        firstNode.setContent(content);
    else {
        MyNode<T> newFirst = new MyNode<T>(content);
        MyNode<T> oldFirst = firstNode;
        firstNode = newFirst;
        newFirst.setNextNode(oldFirst);
        oldFirst.setPreviousNode(newFirst);
    }
    size++;
}

/**
 * Returns an arbitrary item from the linked list
 * 
 * @param index
 *            Index of item to be retrieved from the linked list
 * @return Item residing at index
 */
public T get(int index) {
    return getNode(index).getContent();
}

/**
 * Returns the first item in the linked list
 * 
 * @return First item in the linked list
 */
public T getFirst() {
    return firstNode.getContent();
}

/**
 * Returns the last item in the linked list
 * 
 * @return Last item in the linked list
 */
public T getLast() {
    return lastNode.getContent();
}

/**
 * Returns the node at a given index 
 * @param index Which node to retrieve
 * @return Node at index
 */
private MyNode<T> getNode(int index) {
    if (index < 0 || index >= size)
        throw new NoSuchElementException(index < 0 ? "Negative index"
                : "Index does not exist");

    MyNode<T> which;
    if (index <= size / 2) {
        which = firstNode;
        for (int i = 0; i < index; i++)
            which = which.getNextNode();
    } else {
        which = lastNode;
        for (int i = size - 1; i > index; i--)
            which = which.getPreviousNode();
    }
    return which;
}

/**
 * Inserts an element before an arbitrary point in the list
 * 
 * @param index
 *            Index to element before
 * @param content
 *            What to insert at index
 */
public void insertBefore(int index, T content) {
    if (index == 0) {
        addFirst(content);
        return;
    }

    MyNode<T> currentOcc = getNode(index);
    MyNode<T> prev = currentOcc.getPreviousNode();
    MyNode<T> newGuy = new MyNode<T>(content);
    newGuy.setNextNode(currentOcc);
    newGuy.setPreviousNode(prev);
    prev.setNextNode(newGuy);
    currentOcc.setPreviousNode(newGuy);
    size++;
}

/**
 * Determines if the list is empty
 * 
 * @return If the list is empty
 */
public boolean isEmpty() {
    if (size == 0)
        return true;
    return false;
}

/**
 * Removes the node (and consequently element) at index and "heals" the list
 * 
 * @param index
 *            Location of element to be removed
 */
public void remove(int index) {

    if (index == 0) {
        removeFirst();
        return;
    }

    if (index == size - 1) {
        removeLast();
        return;
    }

    MyNode<T> marked = getNode(index);
    MyNode<T> before = marked.getPreviousNode();
    MyNode<T> after = marked.getNextNode();
    before.setNextNode(after);
    after.setPreviousNode(before);
    marked = null;
    size--;
}

/**
 * Removes first node (and consequently first element) from the list
 */
public void removeFirst() {

    if (size != 1) {
        @SuppressWarnings("unused")
        MyNode<T> temp = firstNode;
        firstNode = firstNode.getNextNode();
        firstNode.setPreviousNode(null);
        temp = null;
    } else
        firstNode.setContent(null);

    size--;
}

/**
 * Removes last node (and consequently last element) from the list
 */
public void removeLast() {
    if (size != 1) {
        @SuppressWarnings("unused")
        MyNode<T> temp = lastNode;
        lastNode = lastNode.getPreviousNode();
        lastNode.setNextNode(null);
        temp = null;
    } else
        lastNode.setContent(null);
    size--;
}

/**
 * Updates the content of a node
 * 
 * @param index
 *            Location of node to update
 * @param content
 *            New content for node
 */
public void set(int index, T content) {
    getNode(index).setContent(content);
}

/**
 * Returns size of node
 * 
 * @return size of node
 */
public int size() {
    return size;
}
}

MyNode

public class MyNode<T> {

private T content;
private MyNode<T> nextNode;
private MyNode<T> previousNode;

/**
 * Constructs a new node without adding content
 */
public MyNode() {
    nextNode = null;
    this.content = null;
    previousNode = null;
}

/**
 * Constructs a new node and sets its content
 * 
 * @param content
 *            Content to occupy new node
 */
public MyNode(T content) {
    nextNode = null;
    this.content = content;
    previousNode = null;
}

/**
 * Returns this node
 * 
 * @return This node
 */
public MyNode<T> get() {
    return this;
}

/**
 * Returns the content of the node
 * 
 * @return The content of the node
 */
public T getContent() {
    return content;
}

/**
 * Returns the next node
 * 
 * @return The next node
 */
public MyNode<T> getNextNode() {
    return nextNode;
}

/**
 * Returns the previous node
 * 
 * @return The previous node
 */
public MyNode<T> getPreviousNode() {
    return previousNode;
}

/**
 * Determines if this is the last node
 * 
 * @return If this is the last node
 */
public boolean isLast() {
    if (nextNode == null)
        return true;
    return false;
}

/**
 * Sets the content of this node
 * 
 * @param content
 *            Content to be given to this node
 */
public void setContent(T content) {
    this.content = content;
}

/**
 * Sets the next node
 * 
 * @param next
 *            The node to be defined as next
 */
public void setNextNode(MyNode<T> next) {
    nextNode = next;
}

/**
 * Sets the previous node
 * 
 * @param previous
 *            Which node is to become the previous node
 * @return the previous node
 */
public MyNode<T> setPreviousNode(MyNode<T> previous) {
    previousNode = previous;
    return previousNode;
}

/**
 * Convenience method that creates a new node and links it after this node
 * 
 * @precondition This is the last node in the list
 * @param content
 * @return
 */
public MyNode<T> spawnNode(T content) {
    nextNode = new MyNode<T>(content);
    nextNode.setPreviousNode(this);
    return nextNode;
}
}


815
10
задан 24 мая 2011 в 02:05 Источник Поделиться
Комментарии
2 ответа

Во-первых, MyNode не собирается быть использован любой класс вне MyLinkedList. Было бы лучше, если бы вы реализовали его как отдельный класс внутри одного и того же файла, как MyLinkedList. Его единственной целью является хранение данных для MyLinkedList, это не объект в своем собственном праве.

Как часть этого, я сделаю все переменные-члены общественных и избавиться от геттера/сеттера. Точка закрытый доступ, чтобы предотвратить внешнему коду подружиться с ним. Но вот только кода с помощью MyNode является MyLinkedList который должен много с ним. Все эти геттеры/сеттеры только осложнит ситуацию.

if (size == 0)
firstNode.setContent(content);
else
lastNode = lastNode.spawnNode(content);

Большинство людей скажут, что вы всегда должны ставить { и } даже в одну линию блоков.

public boolean isEmpty() {
if (size == 0)
return true;
return false;
}

Просто использовать

return size == 0;

Его проще и легче читать.

    @SuppressWarnings("unused")
MyNode<T> temp = firstNode;
firstNode = firstNode.getNextNode();
firstNode.setPreviousNode(null);
temp = null;

Что ты делаешь с температурой? Предупреждение говорит вам, что код с привлечением темп ничего не делает.

В конструкторе вы создаете один пустой узел, для начала, в нескольких местах в коде, у вас есть особый случай, чтобы справиться с этим, сохраняя первое введенное значение в этом узле. Насколько я могу сказать, тебе удалось найти все, если его проблема. Но там, кажется, не быть веские причины, чтобы делать это таким образом.

В целом, ваш код является более сложным, то он должен быть. Например, вы оба insertbefore и insertAfter. Но insertAfter могла быть реализована как метод insertbefore(индекс + 1); у вас есть много разных вставить/удалить методы, когда вы действительно хотите только один. Другие могут быть полезны с точки зрения интерфейса, но все они должны позвонить в единую реализацию. (Если они не могут его реализовать еще более эффективно)

Я предлагаю способ, как следующие

private link_together(MyNode<T> left, MyNode<T> right)
{
if(left != null)
{
left.next = right;
}else{
firstNode = right;
}

if(right != null)
{
right.previous = left;
}else{
lastNode = left;
}
}

Это позволит соединить два узла. Она также будет обрабатывать случаи, когда один из узлов имеет значение null, что означает, что текущий узел является либо в начало или конец списка.

Теперь вставьте становится:

   public void insertBefore(int index, T value)
{
Node<T> new_node = new Node<T>(value);
Node<T> node_after = getNode(index);
// if we are trying to insert at the end of the list
// node_after will be null
Node<T> node_before = node_after : node_after.previous : lastNode;
link_together(node_before, new_node);
link_together(new_node, node_after);
size++;
}

Эта функция может использоваться для вставки узлов в любом месте в списке, даже в начале или в конце или в пустые списки. Аналогичным образом, удаление тоже работает.

public void remove(int index)
{
Node<T> node = getNode(index);
Node<T> node_before = node.previous;
Node<T> node_after = node.next;
link_together(node_before, node_after);
size--;
}

10
ответ дан 24 мая 2011 в 10:05 Источник Поделиться

У меня нет много, чтобы добавить к посту Уинстона.

if (index < 0 || index >= size)
throw new NoSuchElementException(index < 0 ? "Negative index"
: "Index does not exist");

Я справлюсь с оба случая отдельно:

if (index < 0 ) throw new NoSuchElementException("Negative index");
if (index >= size) throw new NoSuchElementException("Index does not exist");

Ваш установите делает три вещи и я бы экстракт getFromTail и getFromHead (как защищенные методы) для лучшего разделения проблем и тестируемости.

6
ответ дан 24 мая 2011 в 11:05 Источник Поделиться