java - 単一連結リストから循環連結リスト

Question

add() メソッドと remove() メソッドを調整して、単一のリンクリストを二重循環リストにしようとしています。

これが私のコードです：

private LLNode<E> head;     // the first node in the list
private LLNode<E> tail;     // the last node in the list

// Adds the specified new item to the back of the list.
public void add(E newData)
{
    if (head == null)   // if the list is empty...
        addToHead(newData);       
    else    
        addAfter(newData, nodeAt(size - 1));
}

// Removes and returns the item at the specified index of the list.
public E remove(int index)
{
    if (index == 0)         // if removing from the head...
        return removeFromHead();
    else
        return removeAfter(nodeAt(index - 1));
}

    private void addToHead(E newItem)
    {
        LLNode<E> newNode = new LLNode<E>();
        newNode.data = newItem;
        newNode.next = head;      
        head = newNode;
        head.prev = tail;
        tail.next = newNode;
        size++;
    }

// Removes the head node from the list.
private E removeFromHead()
{
    if (head != null) {
        E temp = head.data;
        head = head.next;
        head.prev = tail;
        tail.next = head;
        size--;
        return temp;
    } else
        throw new NoSuchElementException();
}

// Adds a new node containing the specified data, after the
//  specified node in the list.
private void addAfter(E newItem, LLNode<E> where)
{
    if (where != null) {
        LLNode<E> newNode = new LLNode<E>();
        newNode.data = newItem;
        newNode.next = where.next;
        where.next = newNode;
        newNode.prev = where;
        size++;
    } else {
        throw new NoSuchElementException();
    }
}

// Removes the node after the specified node in the list.
private E removeAfter(LLNode<E> where)
{
    if (where != null && where.next != null) {
        E temp = where.next.data;
        where.next = where.next.next;
        where.next.prev = where;
        size--;
        return temp;
    } else
        throw new NoSuchElementException();
}

私の主な方法では：

TopSpinLinkedList<Integer> ll = new TopSpinLinkedList<Integer>(numTokens, spinSize);

    //fills LinkedList with tokens
    for(int i = 1; i <= numTokens; i++) {
        ll.add(i);
    }

このメソッドを呼び出そうとすると:

//shifts all elements in LinkedList to left by one
public void shiftLeft()
{
    if(head == null || head.next == null)
        return;
    LLNode<E> temp = new LLNode<E>();
    temp = head;
    head = head.next;
    temp.next = null;
    tail.next = temp;
    tail = temp;
}

実行時に NullPointerException が発生します。私のadd（）およびremove（）メソッドと関係があると確信しています。二重循環リンクリストにするために何が間違っているのか正確にはわかりません。どんな助けでも大歓迎です。

score 1 · Accepted Answer

あなたのaddToHeadメソッドでは、tailあなたがやっているときに変数を初期化したと確信していtail.next = newNodeますか?

これを試して：

private void addToHead(E newItem)
    {
        LLNode<E> newNode = new LLNode<E>();
        newNode.data = newItem;
        head = newNode;
        tail = newNode;
        newNode.prev = newNode.next = newNode;
        size++;
    }

score 0 · Accepted Answer

private void addToHead(E newItem){
    LLNode<E> newNode = new LLNode<E>();
    newNode.data = newItem;

    // head and tail are empty
    head = newNode;
    tail = newNode;
    head.next = newNode;
    tail.next = newNode;
    head.prev = newNode;
    tail.prev = newNode;
}


private void addAfter(E newItem, LLNode<E> where){
    if (where != null) {
        LLNode<E> newNode = new LLNode<E>();
        newNode.data = newItem;


        //this part is what you need
        newNode.next = where;
        newNode.prev = where.prev;
        where.prev.next = newNode; 
        where.prev = newNode;
        size++;
    } else {
        throw new NoSuchElementException();
    }
}

//コードを変更しました。これで動作するはずです。//要素をwhere1 つ右にシフトし、その位置に newNode を挿入しました。

また、二重循環リンクリストを使用している場合は、テールを持つ必要はありません。あなたはそれを取り除くことができます。

score -1 · Accepted Answer

template<class T>
ostream& operator<<(ostream& os, CircularList<T>& ll) 
{
	if(!(ll.isEmpty()))
	{
		os<<"[";
		
		int size=ll.size();
		int counting=0;
		while(counting<size)
		{
			os<<ll.get(counting);
			if(counting+1<size)
				os<<",";
			counting++;
		}
		os<<"]";

	}
	else
	{
		os<<"[]";
	}
}

template<class T>		
CircularList<T>::CircularList()
{
	this->head = NULL;
}

template<class T>
CircularList<T>::CircularList(const CircularList<T>& other) 
{
	this->head=0;
	Node<T>* tempHead=other.getLeader();
	while(tempHead!=0)
	{
		Node<T> *temp = new Node<T>(tempHead->data);
		temp->next = 0;
		Node<T>* curr = this->getLeader();
		if (curr != 0)
		{
			while (curr->next != 0)
			{
			curr = curr->next;
			}
			curr->next = temp;
		}
		else
		{
			this->head = temp;
		}
		tempHead=tempHead->next;
	}
}

template<class T>
CircularList<T>& CircularList<T>::operator=(const CircularList<T>& other) 
{
	if(&other != this)
	{
		this->head=0;
		Node<T>* tempHead=other.head;
		while(tempHead!=0)
		{
			Node<T>* temp = new Node<T>(tempHead->data);
			temp->next = 0;
			Node<T>* curr = this->head;
			if (curr != 0)
			{
				while (curr->next != 0)
				{
				curr = curr->next;
				}
				curr->next = temp;
			}
			else
			{
				this->head = temp;
			}
			tempHead=tempHead->next;
		}
	}
    return *this;	
}

template<class T>
CircularList<T>* CircularList<T>::clone() 
{
	CircularList<T>* circle = new CircularList<T>(*this);
}

template<class T>
CircularList<T>::~CircularList()
{
	int count =size();
	Node<T>* current = this->head;
	int i=0;
	while (i<count)
	{
		Node<T>* next = current->next;
		delete current;
		current = next;
		i++;
	}
this->head = 0;
}
	
template<class T>
void CircularList<T>::insert(int index, T data) 
{
	Node<T> *j= new Node<T>(data);
	
	if((0 <= index) &&( index<= size()))
	{
		if(index==0)
		{
			if(isEmpty())
			{
				this->head=j;
			}
			else
			{
				Node<T>*skipping=this->head;
				this->head=j;
				this->head->next=skipping;	
			}
		}
		else
		{
			Node<T> *tempping =this->head;
			int counting =1;
			while(counting!=index)
			{
				tempping=tempping->next;
				counting++;
			}
			j->next=tempping->next;
			tempping->next=j;
		}
	}
	else
	{
		throw ("invalid index");
	}
}
	
template<class T>
T CircularList<T>::remove(int index)
{
	T pet;
	if(0 <= index && index<= size()-1)
	{
		if(!isEmpty())
		{
			Node<T> *ret=getLeader();
			Node<T>* skip=NULL;
			if(index!=0)
			{
			int i=1;
			while(i!=(index))
			{
				ret=ret->next;
				i++;
			}
			skip=ret;
			pet=get(index);
			ret=ret->next;
			if(ret->next==NULL)
			{
				delete ret;
				skip->next=NULL;
				ret=NULL;
			}
			else
			{
				skip->next=ret->next;
				delete ret;
				ret=NULL;
			}
		}
		else
		{
			    Node<T> *tmp = this->head->next;
			    pet=get(index);
				delete this->head;
				this->head = tmp;
		}
		return pet;
		}
		else
		{
			throw ("Empty list");
		}
	
	}
	else
	{
		throw ("Invalid index");
	}
}
	
template<class T>	
T CircularList<T>::get(int index) const
{
	if(this->head!=NULL)
	{
		if(0 <= index && index<= size()-1)	
		{
			int counting=0;
			Node<T>* p =this->head;
			while(p!=NULL)
			{
				if(counting==index)
				{
					return p->data;
				}
				counting++;
				p=p->next;
			}
	}
		else
		{
		throw ("invalid index");
		}
	}	
	else
	{
		throw("empty list");
	}
}

template<class T>
bool CircularList<T>::isEmpty()
{
	if(this->head==0)
	{
		return true ;
	}
	else
	{
		return false;
	}
}

template<class T>
void CircularList<T>::clear()
{
	Node<T>*serp=this->head;
	while(this->head!=NULL)
	{
		this->head=this->head->next;
		delete serp;
		serp=this->head;
	}
}

template<class T>
Node<T>* CircularList<T>::getLeader() const
{
	return this->head;
}

template<class T>
ostream& CircularList<T>::print(ostream& os)
{
	os<<*this;
}

template<class T>
int CircularList<T>::size() const
{
	int counting=0;
	Node<T> *serp =getLeader();
	while(serp!=NULL)
	{
		serp=serp->next;
		counting++;
	}
	return counting;
}

template <class T>
CircularList<T>& CircularList<T>::operator+(const CircularList<T>& other)
{
	CircularList<T>* serp=new CircularList<T>(*this);
	Node<T>* hey=other.getLeader();
	int counting=serp->size();
	int position=0;
	while(hey!=NULL)
	{
		serp->insert(counting,other.get(position));
		hey=hey->next;
		position++;
		counting++;
	}
	return *serp;
}
//a friend asked me to help him with some assignment i still have the code

java - 単一連結リストから循環連結リスト

3 に答える 3

Related

Reference