`

实现MyLinkedList

 
阅读更多

MyLinkedList:

 

package com.matt;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyLinkedList<AnyType> implements Iterable<AnyType> {
	private int theSize;
	private int modCount = 0;
	private Node<AnyType> beginMarker;
	private Node<AnyType> endMarker;

	private static class Node<AnyType>{
		public Node(AnyType d, Node<AnyType> p, Node<AnyType> n){
			data = d; prev = p; next = n;
		}
		
		public AnyType data;
		public Node<AnyType> prev;
		public Node<AnyType> next;
	}
	
	public MyLinkedList(){
		clear();
	}
	
	public void clear(){
		beginMarker = new Node<AnyType>(null,null,null);
		endMarker = new Node<AnyType>(null, beginMarker,null);
		beginMarker.next = endMarker;
		
		theSize = 0;
		modCount++;
	}
	
	public int size(){
		return theSize;
	}
	
	public boolean isEmpty(){
		return size() == 0;
	}
	
	public boolean add(AnyType x){
		add(size(),x);
		return true;
	}
	
	public void add(int idx, AnyType x){
		addBefore(getNode(idx),x);
	}
	
	public AnyType get(int idx){
		return getNode(idx).data;
	}
	
	public AnyType set(int idx, AnyType newVal){
		Node<AnyType> p = getNode(idx);
		AnyType oldVal = p.data;
		p.data = newVal;
		return oldVal;
	}
	
	public AnyType remove(int idx){
		return remove(getNode(idx));
	}
	
	private void addBefore(Node<AnyType> p, AnyType x){
		Node<AnyType> newNode = new Node<AnyType>(x,p.prev,p);
		p.prev.next = newNode;
		p.prev = newNode;
		
		theSize++;
		modCount++;
	}
	
	private AnyType remove(Node<AnyType> p){
		p.prev.next = p.next;
		p.next.prev = p.prev;
		
		theSize--;
		modCount++;
		
		return p.data;
	}
	
	public Node<AnyType> getNode(int idx){
		Node<AnyType> p;
		
		if(idx <0 || idx>size()) throw new IndexOutOfBoundsException();
		if(idx<size()/2){
			p = beginMarker.next;
			for(int i = 0; i<idx;i++) p = p.next;
		}else{
			p = endMarker;
			for(int i = size();i>idx;i--){
				p = p.prev;
			}
		}
		
		return p;
	}
	
	@Override
	public Iterator<AnyType> iterator() {
		
		return new LinkedListIterator();
	}
	
	private class LinkedListIterator implements Iterator<AnyType>{
		private Node<AnyType> current = beginMarker.next;
		private int expectedModCount = modCount;
		private boolean okToRemove = false;
		
		
		@Override
		public boolean hasNext() {
			
			return current != endMarker;
		}

		@Override
		public AnyType next() {
			if(modCount != expectedModCount) 
				throw new ConcurrentModificationException();
			
			if(!hasNext()) throw new NoSuchElementException();
			
			AnyType nextItem = current.data;
			current = current.next;
			okToRemove = true;
			return nextItem;
		}

		@Override
		public void remove() {
			if(modCount != expectedModCount) 
				throw new ConcurrentModificationException();
			if(!okToRemove) throw new IllegalStateException();
			
			MyLinkedList.this.remove(current.prev);
			okToRemove = false;
			expectedModCount++;
			
		}
		
	}
	
	public String toString(){
		Node<AnyType> p = beginMarker;
		String l = "[";
		for(int i=0;i<size();i++){
			p = p.next;
			if(i<size()-1)
			l = l + p.data + ",";
			else l = l + p.data + "]";
		}
		
		return l;
	}

	public static void main(String [] args){
		MyLinkedList<String> lst = new MyLinkedList<String>();
		lst.add("a");
		lst.add("b");
		lst.add("c");
		
		System.out.println(lst.size());
		lst.remove(1);
		System.out.println(lst);
		
	    Iterator<String> lstIter = lst.iterator();
	    while(lstIter.hasNext()){
	    	String str = lstIter.next();
	    	if(str.equals("b")) lstIter.remove();
	    }
	    System.out.println(lst);
	    
	}
	
}

 

分享到:
评论

相关推荐

    1.MyLinkedList(LinkedList底层实现).md

    MyLinkedList(LinkedList底层实现),自己编写的关于LinkedList的底层实现--双向链表

    MyLinkedList

    Java LinkedList 练习,自己实现Java LinkedList 增删改查功能

    MyLinkedList05.java

    从无到有手写LinkedList,深入理解JDK源码,并实现自己的数据结构。

    MyLinkedList :(我(链接(列表为null)))

    《深入解析Java中的MyLinkedList实现》 在Java编程语言中,`LinkedList`是集合框架中的一种数据结构,它实现了一个双链表,提供了高效的插入、删除操作,但随机访问性能相对较差。本篇文章将深入探讨自定义的`...

    双向链表(java实现)

    在Java中实现双向链表,我们通常会创建一个表示链表节点的类(如`Node`),以及一个表示链表本身的类(如`MyLinkedList`)。`Node`类包含数据和两个引用,分别用于指向前一个节点和后一个节点。`MyLinkedList`类则...

    C# 链表实现

    本篇文章将深入探讨C#中的链表实现,包括链表的基本概念、结构以及如何通过`MyLinkedList.cs`和`Node.cs`这两个文件来创建一个自定义链表。 链表是一种线性数据结构,与数组不同,它的元素可以在内存中的任何位置。...

    Java script实现堆栈和链表

    ### JavaScript 实现堆栈与链表 #### 一、链表实现 在JavaScript中实现链表可以帮助我们更好地理解和掌握数据结构的基本概念。本部分将详细介绍如何通过JavaScript代码实现链表的功能。 ##### 1. 节点构造方法 `...

    C#实现的简单链表类实例

    本文中的类MyLinkedList只是实现了该类的最基本的功能。C#中没有指针,但因为C#中类在赋值时传递的是地址,因此仍然可以利用这点制作一个链表。 二、结点类Node和链表类MyLinkedList代码 /// /// 链表结点 /// ...

    单链表反转 链表相交

    实现了一个简单的java版本的单链表,链表反转和链表是否相交如果相交求相交节点。...然后就在网上找了几个实现思路自己用java做了一个简单的实现.MyLinkedList.java 是链表的实现,Main.java 是测试代码

    mymalloc

    “ mylinkedlist.c”文件包含链表的实现。 在这里,mylinkedlist文件包含在节点中插入元素,在节点中删除第一个元素并在节点中显示元素。 “ mymalloc.h”文件包含malloc和free函数的实现,这些函数包含在...

    java实现单链表增删改查的实例代码详解

    Java语言中,单链表的实现需要创建节点类Node和管理节点的链表类MyLinkedList。接下来,我们详细探讨如何在Java中实现单链表的增加、删除、修改和查询操作。 首先,定义一个节点类Node,它是一个泛型类,表示单链表...

    双向链表.docx

    在提供的代码中,`MyLinkedList` 类是链表的实现,它包含了以下核心方法: 1. **addFirst(Object ele)**:此方法用于在链表的开头插入新节点。如果链表为空(即 `size == 0`),则新节点同时成为头节点和尾节点;...

    2014级软件工程专业数据结构课程设计方案V2.0.docx

    学生需要实现线性表(如MyArrayList和MyLinkedList)、树和图的数据结构,并通过动画展示其基本操作,如插入、删除、查找等。同时,要展示带权图的最小生成树和最短路径算法,如Prim或Kruskal算法。 5. **农夫过河...

    jv-linked-list

    给定实现MyLinkedListInterface MyLinkedList类,实现所有必需的方法。 使您的LinkedList用作java.util.LinkedList (创建Node对象以存储具有到左侧和右侧邻居Node链接的数据)。 您的实现应具有指向第一个和最后一...

    java 动态的数组链表

    在实现动态数组链表时,例如`MyLinkedList.java`可能包含自定义的链表节点类(Node),包含数据和指向下一个节点的引用,以及链表类本身,提供类似ArrayList的操作。`Java.jpg`可能是用于辅助理解链表概念的可视化图...

    2013级软件工程专业数据结构课程设计方案V1.0.docx

    此外,动画演示部分要求学生实现MyArrayList、MyLinkedList、MyStack和MyQueue的操作动画,这不仅需要熟悉这些数据结构的内部工作原理,还需要掌握图形用户界面的设计。无权图的深度优先遍历和广度优先遍历的动画...

Global site tag (gtag.js) - Google Analytics