链表由一系列结点组成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,链表比较方便插入和删除操作。
用链表实现迭代器:
class LinkIter
{
public int iData;
public LinkIter next;
public LinkIter(int data)
{
iData = data;
}
public void displayLink()
{
System.out.println(iData + " ");
}
}
class LinkListIter
{
public LinkIter first;
public LinkListIter()
{
first = null;
}
public boolean isEmpty()
{
return first == null;
}
public LinkIter getFirst()
{
return first;
}
public void setFirst(LinkIter first)
{
this.first = first;
}
public void displayList()
{
LinkIter current = first;
while (current != null)
{
current.displayLink();
current = current.next;
}
}
public ListIterator getIterator()
{
return new ListIterator(this);
}
}
class ListIterator
{
private LinkIter current;
private LinkIter previous;
private final LinkListIter ourList;
public ListIterator(LinkListIter lnk)
{
ourList = lnk;
reset();
}
public void reset()
{
current = ourList.getFirst();
previous = null;
}
public boolean atEnd()
{
return current.next == null;
}
public void nextLink()
{
previous = current;
current = current.next;
}
public LinkIter getLink()
{
return current;
}
//在当前结点后插入,先判断链表是否为空
public void insertAfter(int dd)
{
LinkIter newLink = new LinkIter(dd);
if(ourList.isEmpty())
{
ourList.setFirst(newLink);
current = newLink;
}
else
{
newLink.next = current.next;
current.next = newLink;
nextLink();
}
}
//在当前结点前插入,判断是否是首结点
public void insertBefore(int dd)
{
LinkIter newLink = new LinkIter(dd);
if(previous == null)
{
newLink.next = ourList.getFirst();
ourList.setFirst(newLink);
reset();
}
else
{
newLink.next = previous.next;
previous.next = newLink;
nextLink();
}
}
//删除当前结点,判断是否是首结点
public int deleteCurrent()
{
int data = current.iData;
if(previous == null)
{
ourList.setFirst(current.next);
reset();
}
else
{
previous.next = current.next;
if(atEnd())
reset();
else
current = current.next;
}
return data;
}
注:以上代码均出自 JAVA数据结构与算法 第二版
分享到:
相关推荐
下面是一个简化的迭代器实现示例,这里我们只考虑前向迭代器: ```cpp template class SimpleIterator { public: // 构造函数,初始化为nullptr SimpleIterator() : ptr_(nullptr) {} // 构造函数,初始化为...
具体迭代器实现了迭代器接口,并与具体的聚合类型协同工作。在示例中,有两个具体迭代器类: - `ConcreteIterator1`:实现正向遍历。 - `ConcreteIterator2`:实现反向遍历。 ### 实现细节 - `ConcreteIterator1`...
在"IteratorPatternDemo"这个例子中,我们可以预期看到一个具体的迭代器实现,它可能包含了对某种数据结构(如数组、链表或树)的遍历逻辑。此外,还会有聚合对象的接口,以及至少一个实现了该接口的具体聚合类。...
为了遵循面向接口编程的原则,通常会有容器接口和容器实现类,以及迭代器接口和迭代器实现类。 在迭代器模式的实现中,迭代器接口通常包含以下方法: 1. `hasNext()`: 检查是否还有更多元素可以遍历。 2. `next()`:...
// 具体迭代器实现 private class Itr implements Iterator { int cursor = 0; int lastRet = -1; int expectedModCount = modCount; // 判断是否有下一个元素 public boolean hasNext() { return cursor !...
每个具体的聚合类通常都有一个对应的迭代器实现。 3. **聚合接口**:定义了添加、删除元素以及获取迭代器的方法,但不暴露其内部结构。 4. **具体聚合类**:实现了聚合接口,存储并管理元素对象,同时提供创建迭代器...
3. **具体迭代器实现**:一个派生自`Iterator`的类,如`ConcreteIterator`,它实现了遍历`Container`的逻辑。 4. **客户端代码**:展示如何使用`Container`和`ConcreteIterator`进行遍历的示例。 迭代器模式的优势...
通过上述的节点和迭代器实现,你可以创建和遍历自定义数据结构,这在许多实际编程场景中都是非常有用的。在VS2015中,你可以编写测试代码来验证这些实现的功能性和正确性,确保它们能按预期工作。 总结起来,节点和...
模拟vector,Constructors, operators, assign, at, back, begin, clear, empty, end, erase, front, insert, pop_back, push_back, reserve, resize, size, swap,迭代器实现。
3. **具体迭代器实现**:根据聚合对象的内部结构实现迭代逻辑,可能使用了链表、数组或其他数据结构。 4. **具体聚合对象实现**:实现聚合对象接口,提供内部数据结构和创建具体迭代器的方法。 迭代器模式的优势...
每个具体的聚合对象都会有一个对应的迭代器实现。 4. **客户端(Client)**:使用迭代器来遍历聚合对象的元素,不需要了解聚合对象的内部结构。 在"设计模式的迭代器模式的例子"中,可能包含以下代码结构: 首先,...
2. **支持多种遍历方式**:不同的迭代器实现可以支持不同的遍历策略,比如正向遍历、反向遍历,甚至非线性遍历。 3. **增加新的聚合类和迭代器类更加灵活**:迭代器模式采用抽象迭代器,使得新增迭代器类或聚合类对...
通过使用迭代器,我们可以有效地遍历和操作集合中的元素,同时,Java的并发库提供了适应多线程环境的迭代器实现,以满足各种编程需求。这个小例子展示了如何在实际编程中使用迭代器,帮助我们更好地理解和运用这些...
此外,迭代器模式还支持多种遍历方式,如深度优先和广度优先,只需提供不同的迭代器实现即可。 在“IteratorPatternDemo”示例中,可能会包含以下内容: 1. **创建聚合对象**:首先,我们需要创建一个聚合对象类,...
每个具体的聚合类都有一个与之对应的迭代器实现。 4. **客户端(Client)角色**:使用迭代器来遍历聚合对象。 **迭代器模式的优势:** - **分离遍历操作和聚合对象**:迭代器模式将遍历操作的责任从聚合类中分离...
对于每个不同的聚合类,可能存在一个对应的迭代器实现。 4. **具体聚合类(Concrete Aggregate)**:实现聚合类接口,通常包括创建和管理迭代器的方法,如`createIterator()`。在C++的STL中,容器类如`std::vector`...
在此“基于迭代器的一元多项式计算”项目中,我们探讨的是如何使用C语言实现一个一元多项式计算的迭代器,同时利用分层结构来组织代码,提高代码的可读性和可维护性。 首先,一元多项式是数学中的基本概念,由常数...
迭代器模式在Java集合框架中广泛应用,例如`ArrayList`、`LinkedList`、`HashSet`等都实现了`Iterable`接口,并提供了各自的迭代器实现。这些集合类的迭代器各自有不同的性能特点。例如,`ArrayList`的迭代器速度快...
在我们的“迭代器Demo”项目中,可能包含了一个或多个这样的迭代器实现,演示了如何在实际应用中使用它们。例如,可能有一个自定义的数据结构,如一个堆或者树,我们可以通过迭代器轻松地遍历其中的所有元素。 迭代...
上述代码展示了基本的迭代器实现。`Node`结构体代表链表中的每个节点,包含了数据和指向前后节点的指针。`ListIterator`类的构造函数接收一个指向`Node`的指针,`operator++`和`operator--`负责改变`current`指针。`...