`
bo_hai
  • 浏览: 564659 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

非循环单向链表JAVA实现

 
阅读更多

一、自定义迭代器。链表用来存储数据，就必须有访问的数据的工具。代码如下：

import java.util.Iterator;

public interface SingleListIterator<E> extends Iterator<E> {

	boolean hasNext();
	
	E next();
	
	void remove();
	
	void set(E e);
	
	void add(E e);
}

 二、链表实现如下：

import java.util.List;

public class SingleLinkedList<E> extends AbstractSingleLinkedList<E> implements List<E> ,java.io.Serializable {

	private static final long serialVersionUID = -3146637576067909980L;

	private transient Entry<E> header = null;
	private transient int size ;
	// 指向最未端
	private transient Entry<E> lastElement = null;
	
	@Override
	public SingleListIterator<E> singleListIterator() {
		return  new SingleIterator();
	}

	public SingleLinkedList() {
		header = new Entry<E>(null, null);
		lastElement = header;
		size ++;
	}
	
	public E getLast() {
		return lastElement.element;
	}
	
	@Override
	public boolean remove(Object o) {
		boolean result = false;
		if (o == null) {
			for (Entry<E> beforElement = header; beforElement != null; beforElement = beforElement.next) {
				Entry<E> e = beforElement.next;
				if (e != null && e.element == null) {
					beforElement.next = e.next;
					result = true;
					if (e.equals(lastElement)) {
						lastElement = beforElement;
					}
					size --;
				}
			}
		} else {
			for (Entry<E> beforElement = header; beforElement != null; beforElement = beforElement.next) {
				Entry<E> e = beforElement.next;
				if (e != null && o.equals(e.element)) {
					beforElement.next = e.next;
					result = true;
					if (e.equals(lastElement)) {
						lastElement = beforElement;
					}
					size --;
				}
			}
		}
		return result;
	}
	
	@Override
	public E remove(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("Index: "+index+
                    ", Size: "+size);
		}
		Entry<E> e = header;
		Entry<E> before = header;
		for (int i = 0; i < index; i++) {
			before = before.next;
		}
		e = before.next;
		before.next = e.next;
		if (index == size() -1) {
			lastElement = before;
		}
		size --;
		return e.element;
	}	
	
	@Override
	public void add(int index,E element) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("Index: "+index+
                    ", Size: "+size);
		}
		Entry<E> e = header;
		Entry<E> before = header;
		for (int i = 0; i < index; i++) {
			before = before.next;
		}
		e = before.next;
		before.next = new Entry<E>(element, e);
		size ++;
	}

	@Override
	public boolean add(E e) {
		lastElement.next = new Entry<E>(e, null); 
		lastElement = lastElement.next;
		size ++;
		return true;
	}
	
	@Override
	public E get(int index) {
		return entry(index).element;
	}
	
	private Entry<E> entry(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("Index: "+index+
                    ", Size: "+size);
		}
		Entry<E> e = header;
		for (int i = 0; i <= index; i++) {
			e = e.next;
		}
		return e;
	}
	
	@Override
	public int size() {
		return size - 1;
	}

	private static class Entry<E> {
		E element;
		Entry<E> next;
		public Entry(E element, Entry<E> next) {
			this.element = element;
			this.next = next;
		}
	}
	
	private class SingleIterator implements SingleListIterator<E> {
		
		// 最后访问的结点
		private Entry<E> lastReturned = header.next;
		// 中间访问的结点
		private Entry<E> beforeElement = header;
		// 最前访问的结点
		private Entry<E> previousElement = beforeElement;
		
		@Override
		public boolean hasNext() {
			// 非循环单链表最后是null
			return lastReturned != null;
		}

		@Override
		public E next() {
			previousElement = beforeElement;
			beforeElement = lastReturned;
			E e = lastReturned.element;
			lastReturned = lastReturned.next;
			return e;
		}

		@Override
		public void remove() {
			previousElement.next = lastReturned;
			// 删除的是中间的结点，删除完后，中间的结点指向最前结点
			beforeElement = previousElement;
			size --;
		}

		@Override
		public void set(E e) {
			beforeElement.element = e;
		}

		@Override
		public void add(E e) {
			// 若前后结点与中单结点相等，是在执行删除后，接着执行add操作
			if (previousElement == beforeElement) {
				previousElement.next = beforeElement = new Entry<E>(e, lastReturned);
			} else {
				previousElement.next = new Entry<E>(e, beforeElement);
			}
			size ++;
		}
	}
}

三、 测试数据如下：

import java.util.ArrayList;
import java.util.List;



public class SingleLinkedListTest {

	public static void main(String[] args) {
		SingleLinkedList<Integer> arr = new SingleLinkedList<Integer>();
		arr.add(456);
		arr.add(789);
		arr.add(0,123);
		arr.add(789);
		arr.add(741);
		//arr.remove(3);
		arr.add(963);
		
		SingleListIterator<Integer> it = arr.singleListIterator();
		
		System.out.println(arr.size());
		
		List<Integer> remove = new ArrayList<Integer>();
		remove.add(789);
		
		while (it.hasNext()) {
			Integer val = it.next();
			if (remove.contains(val)) {
				it.remove();
			}
		}
		
		for (Integer integer : arr) {
			System.out.println(integer);
		}
		
		System.out.println(arr.size());
	}
}

 四、优点：最初的想法是用来锻炼自己的算法设计能力。写完后，发现SingleLinkedList 比 LinkedList 在插入数据的效率略高，理由是：SingleLinkedList 有一个lastElement 变量，指高链表的最后，而 LinkedList 在插入时，要进行循环遍历。

 欢迎大家指点。

分享到：
| 二分查找的两种实现方法
评论
5 楼 bo_hai 2014-03-31  
弦走向 写道
您并没有把所有的代码帖上去，如：AbstractSingleLinkedList<E> 抽象类。 尽管如此。具体的实现已经写的很清楚。一个lastElement 确实提高了效率。
不过您的迭代器中remove()方法写错了。
public void remove() {
previousElement.next = lastReturned; 
beforeElement = lastReturned;
lastReturned = lastReturned.next;
            size --; 
}

您可否把 您数据结构与算法的源代码打包发给我一份。 因为部分却少的代码看着很费力、
baiwoyidao@163.com 是我邮箱。 感激不尽


文章中加入了附件。请下载。
4 楼 bo_hai 2014-03-31  
弦走向 写道
您并没有把所有的代码帖上去，如：AbstractSingleLinkedList<E> 抽象类。 尽管如此。具体的实现已经写的很清楚。一个lastElement 确实提高了效率。
不过您的迭代器中remove()方法写错了。
public void remove() {
previousElement.next = lastReturned; 
beforeElement = lastReturned;
lastReturned = lastReturned.next;
            size --; 
}

您可否把 您数据结构与算法的源代码打包发给我一份。 因为部分却少的代码看着很费力、
baiwoyidao@163.com 是我邮箱。 感激不尽


年前写的，现在没空整理了。有不明白的，在这里问，我尽力回复。
3 楼 bo_hai 2014-03-31  
弦走向 写道
您并没有把所有的代码帖上去，如：AbstractSingleLinkedList<E> 抽象类。 尽管如此。具体的实现已经写的很清楚。一个lastElement 确实提高了效率。
不过您的迭代器中remove()方法写错了。
public void remove() {
previousElement.next = lastReturned; 
beforeElement = lastReturned;
lastReturned = lastReturned.next;
            size --; 
}

您可否把 您数据结构与算法的源代码打包发给我一份。 因为部分却少的代码看着很费力、
baiwoyidao@163.com 是我邮箱。 感激不尽



在二楼回复您了。谢谢你这么认真的看。
2 楼 bo_hai 2014-03-31   

import java.util.AbstractList;
import java.util.Iterator;

public abstract class AbstractSingleLinkedList<E> extends AbstractList<E> {

	protected AbstractSingleLinkedList(){}
	
	
	@Override
    public Iterator<E> iterator() {
        return singleListIterator();
    }
    
	/**
	 * 返回类型不对
	 * @return
	 */
	public abstract Iterator<E> singleListIterator();
	
}
1 楼 弦走向 2014-03-30  
您并没有把所有的代码帖上去，如：AbstractSingleLinkedList<E> 抽象类。 尽管如此。具体的实现已经写的很清楚。一个lastElement 确实提高了效率。
不过您的迭代器中remove()方法写错了。
public void remove() {
previousElement.next = lastReturned; 
beforeElement = lastReturned;
lastReturned = lastReturned.next;
            size --; 
}

您可否把 您数据结构与算法的源代码打包发给我一份。 因为部分却少的代码看着很费力、
baiwoyidao@163.com 是我邮箱。 感激不尽
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    java编写的循环链表来实现约瑟夫环

    循环链表 实现约瑟夫环 java 自己写的 测试通过 有注释

    单向循环链表（JAVA）

    类似约瑟夫环问题。有一群人组成一个圈。从头开始按照顺时针方向从1开始依次报数。报到到9的人就离开圈子。其左手边的人接着从1开始报数。依此进行，直到剩最后一个人为止。

    循环链表的java实现

    在Java中实现循环链表，我们需要定义一个节点类（Node）来存储数据和指向下一个节点的引用，同时在链表类（CircularLinkedList）中维护头节点和当前大小。以下是实现的关键点： 1. **节点类(Node)**：创建一个内部...

    单向循环链表.zip

    总结来说，这个压缩包提供的源代码为我们展示了如何在Java中实现单向循环链表的数据结构，并通过`List`接口提供了丰富的操作方法。通过学习和理解这些代码，开发者可以深入理解链表的工作原理，并能熟练运用到实际...

    java实现的单向链表和双向链表

    本篇将深入探讨由Java实现的单向链表和双向链表。 首先，我们来理解单向链表。单向链表中的每个节点包含两部分：数据域（存储实际数据）和指针域（存储指向下一个节点的引用）。这种结构使得链表只能向前遍历，不能...

    数据结构-链表 JAVA语言实现

    数据结构-链表 JAVA语言实现,包含单向链表、双向链表、循环链表的遍历、删除和插入 详细介绍：http://blog.csdn.net/z740852294/article/details/77369439

    java链表重发现循环代码

    Amazon 面试题，如何用O(N)实现在链表中找出 是否出现循环(Loop)，算法也可以用在其他语言（C,C++等）

    单向循环链表之自己动手.py

    python单向循环链表

    如何实现一个高效的单向链表逆序输出.docx

    这里我们将探讨如何高效地实现单向链表的逆序输出。 1. 迭代方法： 在提供的参考答案中，使用了迭代的方式来实现链表的逆序输出。首先定义链表节点结构`node`，包含一个整型数据成员`data`和一个指向下一个节点的...

    简单的双向循环链表

    双向循环链表与单向链表不同，它在每个节点中不仅保存了指向下一个节点的指针，还保存了指向前一个节点的指针，这种设计使得在链表中的前后移动更为便捷。在循环链表中，最后一个节点会指向第一个节点，形成一个闭合...

    试析用Java实现链表数据结构.pdf

    3. 链表数据结构：介绍了链表的基本概念，包括数据域、指针域、单向链表、双向链表和循环链表的区别。 4. 链表的Java实现：通过具体的Java代码示例，说明了如何实现链表的基本操作，包括创建节点、链表的遍历、删除...

    链表的原理及java实现代码示例

    "链表的原理及Java实现代码示例" 链表是一种基本的数据结构，它的实现原理不同于数组。链表的优点是插入和删除操作效率高，而缺点是循环遍历时效率不高。Java中使用的LinkedList的实现原理就是链表。 单向链表的...

    Java集合，HashMap底层实现和原理（1.7数组+链表与1.8+的数组+链表+红黑树） 数组和链表.pdf

    链表可以分为单向链表、单向循环链表、双向链表和双向循环链表四种。单向链表就是通过每个节点的指针指向下一个节点从而链接起来的结构。单向循环链表和单向链表的不同是，最后一个节点的next不是指向null，而是指向...

    C语言基于单向链表的图书管理系统源码.zip

    在本压缩包"C语言基于单向链表的图书管理系统源码.zip"中，包含了一个用C语言实现的图书管理系统。这个系统使用了数据结构中的单向链表来存储和管理图书信息，使得我们可以进行诸如添加、删除、查找和显示图书等操作...

    整数链表

    链表可以分为单向链表、双向链表和循环链表。在整数链表的例子中，我们可能使用的是单向链表，因为只包含指向下一个节点的指针。双向链表每个节点还包含一个指向前一个节点的指针，而循环链表则将最后一个节点的指针...

    链表的概念、链表的优势、链表的c语言和java语言的实现

    链表有多种变体，如单向链表、双向链表和循环链表。单向链表中，每个节点只有一个指针指向下一个节点，而双向链表则每个节点都有两个指针，分别指向前一个和后一个节点，这使得在双向链表中可以更灵活地进行前后遍历...

    Java链表实现三例绝对经典.doc

    链表分为单向链表和双向链表，这里我们讨论的是单向链表。 **案例一**： 这个案例展示了链表的基本构建。`Node`类定义了链表的节点，包含一个`name`属性和一个指向下一个节点的`next`引用。`Link`类主要用于链表的...

    链表----链表构造

    ### 链表构造知识点详解 #### 一、链表基本概念 链表是一种常见的线性...以上是关于单向链表构造的基本知识点及其对应的Java实现代码。这些方法提供了对链表的基本操作能力，可以在此基础上进行更复杂的功能开发。

    LinkedList:该项目提供了单向、双向和循环链表的示例

    本项目涵盖了单向链表、双向链表和循环链表三种类型，它们各自有不同的特点和用途。 1. **单向链表**： 单向链表只允许从一个方向遍历，每个节点包含两部分：数据元素和指向下一个节点的引用。在Java中，可以定义...

Magicbox
Global site tag (gtag.js) - Google Analytics