`
天使的左手
  • 浏览: 55457 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

java单链表-带头结点和不带头结点单链表的简单实现

    博客分类:
  • java
阅读更多
带头结点的单链表实现
public class LinkedList<T> {
	private Entry<T> head, tail; //头指针,尾指针  
	private int size; //通过一个变量记录链表长度 

	public LinkedList() {
       //生成一个头结点,让头指针和尾指针都指向它  
		head = tail = new Entry<T>(null);
		size = 0;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return head.next == null; //当头结点的next为空,表明整个链表为空
	}

	public T get(int index) {
		return current(index).element;
	}

	public T set(int index, T element) {
		Entry<T> entry = current(index);
		T oldVal = entry.element;
		entry.element = element;
		return oldVal;
	}

    //默认在原链表尾部添加新的结点
	public boolean add(T element) {
		Entry<T> newEntry = new Entry<T>(element);
		tail.next = newEntry;//原链表尾指针的next指向新的结点  
		tail = newEntry;//尾指针向后移动一位,指向新的结点  
		size++;
		return true;
	}

	public boolean add(int index, T element) {
        //若索引值和链表长度一样,新结点添加到链表最后位置  
		if (index == size)
			return add(element);

        //得到索引index的前一个结点
		Entry<T> preEntry = previous(index);
        //新结点的next为preEntry的next指向的结点
		Entry<T> newEntry = new Entry<T>(element, preEntry.next);
        //preEntry的next指向新的结点
		preEntry.next = newEntry;
		size++;
		return true;
	}

	public T remove(int index) {
        //得到索引index的前一个结点
		Entry<T> preEntry = previous(index);
		T oldVal = preEntry.next.element;
        //如果preEntry的next刚好是最后一个结点,修改tail为preEntry 
		if (preEntry.next == tail)
			tail = preEntry;
		preEntry.next = preEntry.next.next;
		size--;
		return oldVal;
	}

	public void clear() {
		head.next = null;
		tail = head;
		size = 0;
	}

	public String toString() {
		String result = "[";
		Entry<T> entry = head.next;
		while (entry != null) {
			result += entry.element;
			entry = entry.next;
			if (entry != null)
				result += ", ";
		}
		return result + "]";
	}

    //获得索引index对应的entry 
	public Entry<T> current(int index) {
		checkIndexBounds(index);
		Entry<T> entry = head.next;//从第一个结点开始遍历
		int c = 0;
		while (entry != null && c < index) {
			entry = entry.next;
			c++;
		}
		return entry;
	}

    //获得索引index-1对应的entry  
	public Entry<T> previous(int index) {
		checkIndexBounds(index);
		Entry<T> entry = head;//从头结点开始遍历,头指针指向头结点 
		int c = 0;
		while (entry.next != null && c < index) {
			entry = entry.next;
			c++;
		}
		return entry;
	}

	private void checkIndexBounds(int index) {
		if (index < 0 || index >= size)
			throw new IndexOutOfBoundsException("[index: " + index + ", size: "
					+ size + "]");
	}

    //结点对象  	
	private static class Entry<T> {
		T element;
		Entry<T> next;

		public Entry(T element) {
			this(element, null);
		}

		public Entry(T element, Entry<T> next) {
			this.element = element;
			this.next = next;
		}
	}
}


不带头结点的单链表实现
public class LinkedList<T> {
	private Entry<T> head, tail;
	private int size;

	public LinkedList() {
		head = tail = null;
		size = 0;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return head == null; //头指针为空,表示整个链表为空
	}

	public T get(int index) {
		return current(index).element;
	}

	public T set(int index, T element) {
		Entry<T> entry = current(index);
		T oldVal = entry.element;
		entry.element = element;
		return oldVal;
	}

	public boolean add(T element) {
		Entry<T> newEntry = new Entry<T>(element);
		if (head == null) //如果头指针为空,直接将新结点赋值给头指针和尾指针
			head = tail = newEntry;
		else {
			tail.next = newEntry; //否则,尾指针的next指向新的结点,尾指针后移一位,指向新的结点
			tail = newEntry;
		}
		size++;
		return true;
	}

	public boolean add(int index, T element) {
       //若索引值和链表长度一样,新结点添加到链表最后位置  
		if (index == size)
			return add(element);
        
		//获得索引值为index-1的结点
		Entry<T> preEntry = previous(index);
		Entry<T> newEntry = new Entry<T>(element);
		if (preEntry == null) { //index=0 直接操作头指针
			newEntry.next = head;
			head = newEntry;
		} else { //其他情况,用获得的前一个结点完成添加操作
			newEntry.next = preEntry.next;
			preEntry.next = newEntry;
		}
		size++;
		return true;
	}

	public T remove(int index) {
        //获得索引值为index-1的结点
		Entry<T> preEntry = previous(index);
		T oldVal;
		if (preEntry == null) {//index=0 直接操作头指针
			oldVal = head.element;
			head = head.next;
		} else { //其他情况,用获得的前一个结点完成移除操作
			oldVal = preEntry.next.element;
            //如果preEntry的next刚好是最后一个结点,修改tail为preEntry 			
			if (tail == preEntry.next)
				tail = preEntry;
			preEntry.next = preEntry.next.next;
		}
		size--;
		return oldVal;
	}

	public void clear() {
		head = tail = null;
		size = 0;
	}

	public String toString() {
		String result = "[";
		Entry<T> entry = head;
		while (entry != null) {
			result += entry.element;
			entry = entry.next;
			if (entry != null)
				result += ", ";
		}
		return result + "]";
	}

	public Entry<T> current(int index) {
		checkIndexBounds(index);
		Entry<T> entry = head;
		int c = 0;
		while (entry != null && c < index) {
			entry = entry.next;
			c++;
		}
		return entry;
	}

	public Entry<T> previous(int index) {
		checkIndexBounds(index);
		if (index == 0) //索引为0 直接返回null,表明直接用头指针完成操作即可
			return null;

		Entry<T> entry = head;
		int c = 0;
		while (entry.next != null && c < index - 1) {
			entry = entry.next;
			c++;
		}
		return entry;
	}

	private void checkIndexBounds(int index) {
		if (index < 0 || index >= size)
			throw new IndexOutOfBoundsException("[index: " + index + ", size: "
					+ size + "]");
	}

	private static class Entry<T> {
		T element;
		Entry<T> next;

		public Entry(T element) {
			this(element, null);
		}

		public Entry(T element, Entry<T> next) {
			this.element = element;
			this.next = next;
		}
	}
}
分享到:
评论

相关推荐

    用Java编写不带头结点的链表

    在本主题中,我们将探讨如何在Java中实现一个不带头结点的单链表。 首先,我们需要定义链表节点类。一个不带头结点的链表意味着我们不会有一个额外的节点作为列表的起点,第一个节点就是列表的头。以下是一个简单的...

    Java实现带头结点的单链表

    Java实现带头结点的单链表 Java实现带头结点的单链表是一种链式数据结构,链表的...Java实现带头结点的单链表是一种重要的数据结构,它可以用来实现各种数据的存储和管理。通过链表的实现,可以更好地管理和维护数据。

    假设以带头结点的循环链表表示一个队列,并且只设一个队尾指针指向尾元素结点(注意不设头指针),试写出相应的置空队、入队、出队的算法 (Java)

    假设以带头结点的循环链表表示一个队列,并且只设一个队尾指针指向尾元素结点(注意不设头指针),试写出相应的置空队、入队、出队的算法。(Java描述)

    数据结构单链表插入、删除和修改实验报告

    1.理解数据结构中带头结点单链表的定义和逻辑图表示方法。 2.掌握单链表中结点结构的JAVA描述。 3.熟练掌握单链表的插入、删除和查询算法的设计与JAVA实现。 4.熟练掌握简单的演示菜单与人机交互设计方法。 二、...

    设ha和hb分别是指向两个带头结点:两个有序链表的合并

    设ha和hb分别是指向两个带头结点的非递减(递增)有序单链表的头指针。要求设计一个算法,将这两个有序链表合并成一个非递增(递减)有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它存储...

    JAVA单链表的简单操作(递增单链表插入数据,链表逆置,链表逆序合成)

    给定一个按整数值递增排序的带头结点的动态单链表L,我们需要在链表中插入值为x的结点,保持链表的有序性。为了实现这一操作,我们可以遍历链表,找到适当的位置将新结点插入。以下是一个简单的实现: ```java ...

    1_链表_

    实际的编程实现可能会根据所使用的编程语言有所不同,例如,C 语言的实现可能需要考虑指针操作,而 Java 或 Python 等高级语言可以使用对象和引用。在提供的 1.c 文件中,可能包含了这个功能的具体 C 语言实现,而 1...

    数据结构实验1_数据结构实验1_数据结构实验_

    3. 设计和实现二分查找树,以及查找、插入和删除操作。 4. 创建一个简单的散列表,研究冲突解决策略,如开放寻址法和链地址法。 5. 分析和比较不同数据结构的性能,如时间复杂度和空间复杂度。 实验结果截图是对...

    java实现单链表

    单链表(带头结点) 逻辑结构示意图如下 单链表的添加(创建): 1)先创建一个head 头节点,头结点不存放具体的数据, 作用就是表示单链表的头。 2) 后面我们每添加一个节点,就直接加入到 链表的最后。 如果需要...

    数据结构复习整理

    本篇文章主要介绍了数据结构的几个重要知识点,包括顺序表、单链表、带头结点的单链表等数据结构的算法实现。这些算法涵盖了插入、删除、统计元素个数、求和等操作。 1. 顺序表插入算法: 在顺序表 L 中插入一个...

    单链表的详细讲解

    1. **不带头结点的单链表**: 在这种情况下,链表可能只有一个元素或者为空。头指针直接指向首元素结点。 2. **带头结点的单链表**: 这种设计在首元素结点之前附加了一个头结点。头指针指向这个头结点。 #### 四、头...

    数据结构(java版)习题解答

    **习2.9:建立按升序排序的单链表(不带头结点)** - **题目**:建立一个升序排序的单链表。 - **解答**:在添加新节点时,需要保证节点按升序排列。 **习2.10:实验2.6带头结点的循环双链表类,实现线性表接口** -...

    java 版本循环链表

    在提供的文件信息中,虽然标题和描述部分未给出具体内容,但是“java 版本循环链表”的标题和部分描述内容暗示了文章内容应该是与Java编程语言实现的循环链表数据结构相关。循环链表是一种常见的数据结构,在计算机...

    数据结构(Java版)(第2版)习题解答

    【习2.9】 建立按升序排序的单链表(不带头结点)。 8 【习2.10】 实验2.6 带头结点的循环双链表类,实现线性表接口。 10 【习2.11】 实验2.5 建立按升序排序的循环双链表。 14 第3章 栈和队列 17 【习3.1】 习3-5 ...

    数据结构课件及程序(java版)适合初学者学习使用

    这个压缩包中包含的资料是针对初学者设计的,旨在帮助他们理解并掌握数据结构的基本概念和实现方法,主要使用的编程语言是Java。下面我们将逐一解析每个文档可能涵盖的知识点。 1. **单链表类.doc**: - 单链表:...

    2012广西壮族自治区java版本入门.docx

    给定一个带头结点的单链表,每个结点包含一个整型域 `info` 和指向下一个结点的指针域 `next`。设计一个算法删除单链表中所有重复出现的结点,使得 `info` 域相等的结点只保留一个。 **解决思路**: 通过两个指针...

    数据结构(Java版) 线性表的实现与应用完整版 (2).pdf

    这里,你需要实现一个带头结点的单链表类`SinglyList&lt;T&gt;`,并提供以下基本操作: 1. 检查列表是否为空(`isEmpty()`) 2. 获取元素(`get(int index)`) 3. 查找元素位置(`indexOf(T key)`) 4. 输出链表元素(`...

    数据结构复习题

    7. 循环链表判断:带头结点的循环链表h为空的条件是h-&gt;next==h。 8. 无向完全图的边数:n个顶点的无向完全图的边数为n*(n-1)/2。 9. 数组存储:数组M按行优先存储,M[8][5]的起始地址为EA+8*(10*3)+5*3;按列优先...

    数据结构与算法期末考试复习试题.docx

    6. 空链表的判定:不带头结点的单链表为空的条件是head==NULL,而带头结点的单链表为空的条件是head-&gt;next==NULL。 7. 最佳存储结构:如果最常用的操作是在最后一个结点之后插入或删除,使用带头结点的双循环链表...

    单链表的反转

    链表主要分为两种类型:带头结点的链表和不带头结点的链表。头结点是一个特殊的节点,它的next域指向链表的第一个实际数据节点。 单链表的反转是一个常见的操作,它将链表中的前后顺序颠倒,使得原链表的最后一个...

Global site tag (gtag.js) - Google Analytics