实现简答LinkedList

package com.表栈和队列;

import java.util.Iterator;

/**

* 实现LinkedList

* 60页

* @author zj

*

* @param <T>

*/

public class MyLinkedList<T> implements Iterable<T>{

private int theSize; //集合大小

private int modCount = 0;//代表自从构造以来对链表所做的改变次数

private Node<T> beginMarker;//头节点

private Node<T> endMarker;//尾节点

/**

*

* 连接到前一个node和下一个Node

* @author Administrator

*

* @param <T>

*/

private static class Node<T>{

public T data;

public Node<T> prev;//上一个链

public Node<T> next;//下一个链

public Node(T d ,Node<T> p,Node<T> n){

data = d ;

prev = p ;

next = n;

}

}

public MyLinkedList(){

clear();

}

private void clear() {

// TODO Auto-generated method stub

beginMarker = new Node<T>(null, null, null);

endMarker = new Node<T>(null, beginMarker, null);

beginMarker.next = endMarker;

theSize = 0;

modCount++;

}

private int size(){

return theSize;

}

public boolean isEmpty(){

return size() == 0;

}

public boolean add(T t){

add(size(),t);

return true;

}

private void add(int idx, T t) {

// TODO Auto-generated method stub

addBefore( getNode( idx ), t );

}

private T get(int idx){

return getNode(idx).data;

}

private T set(int idx,T newVal){

Node<T> p = getNode(idx);

T  oldVal = p.data;

p.data = newVal;

return oldVal;

}

public T remove(int idx){

return remove(getNode(idx));

}

private T remove(Node<T> p) {

// TODO Auto-generated method stub

p.next.prev = p.prev;

p.prev.next = p.next;

theSize--;

modCount++;

return p.data;

}

/**

* 从下标0开始计算

* 通过获取一个新节点,然后改变指针完成一个双链表的插入操作

* @param p

* @param t

*/

private void addBefore(Node<T> p, T t) {

// TODO Auto-generated method stub

Node<T> newNode = new Node<T>(t,p.prev,p);

newNode.prev.next = newNode;//新节点的上一个节点中指向下一节点的位置

p.prev = newNode;//插入位置节点指向上一节点的位置

theSize++;

modCount++;

}

/*

* 根据索引获取节点

* 如果索引在表的前半部分,那么将向后的方向遍历链表

* 否则将向末尾往回遍历

*/

private Node<T> getNode(int idx) {

// TODO Auto-generated method stub

Node<T> 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<T> iterator() {

// TODO Auto-generated method stub

return new LinkedListIterator();

}

private class LinkedListIterator implements java.util.Iterator<T>{

private Node<T> current = beginMarker.next; //当前节点

private int expectedModCount = modCount;

private boolean okToRemove = false;

@Override

public boolean hasNext() {

// TODO Auto-generated method stub

return current!= endMarker;//当前节点是否等于最后节点

}

@Override

public T next() {

// TODO Auto-generated method stub

if(modCount != expectedModCount)

throw new java.util.ConcurrentModificationException();

if(!hasNext())

throw new java.util.NoSuchElementException();

T nextItem = current.data;

current = current.next;

okToRemove = true;

return nextItem;

}

@Override

public void remove() {

// TODO Auto-generated method stub

if(modCount != expectedModCount)

throw new java.util.ConcurrentModificationException();

if(!okToRemove)

throw new IllegalStateException();

MyLinkedList.this.remove(current.prev);

okToRemove = false;

expectedModCount++;

}

}

public static void main(String[] args) {

MyLinkedList<Integer> ml = new MyLinkedList<Integer>();

ml.add(1);

ml.add(2);

ml.add(3);

ml.add(1, 10);

for(Integer i :ml){

System.out.println(i);

}

}

}

时间: 06-04

实现简答LinkedList的相关文章

Java 实现简答的单链表的功能

作者:林子木  博客网址:http://blog.csdn.net/wolinxuebin 参考网址:http://blog.csdn.net/sunsaigang/article/details/5751780 描述:使用java实现简答的单链表的功能 定义了一个MyList类 包含的函数: getHead()返回头指针: isEmpty() 判断是否为空: addFirst(T element)在链表的头部加入元素: addLast(T element)在链表的尾部加入元: add(T fi

jquery easyui树的简答构造+动态生成js全局变量

jquery easyui树的简答构造: JSP页面 组织机构: <input id="p_organId" name="p_organId" style="width: 160px;height: 28px;"> function loadOrgan(){ organ_combotree = $("#p_organId").combotree({ url:'${ctxFront}/cust/tree', mult

【Python】安装python包时遇到&quot;error: Microsoft Visual C++ 9.0 is required&quot;的简答

简答 在Windows下用pip安装Scrapy报如下错误, error: Microsoft Visual C++ 9.0 is required (Unable to find vcvarsall.bat). Get it from http://aka.ms/vcpython27 打开http://aka.ms/vcpython27会跳转到http://www.microsoft.com/en-us/download/confirmation.aspx?id=44266 将安装包(VCFo

linux系统运维面试题简答

1.     简述常用高可用技术 解答: Keepalived:Keepalived是一个保证集群高可用的服务软件,用来防止单点故障,使用VRRP协议实现.在master和backup之间通过master主动降低自己的权值或者backup检测到master出现故障时,backup将会接管master的工作,继续服务. HAproxy:HAProxy提供高可用性.负载均衡以及基于TCP和HTTP应用的代理,支持虚拟主机,它是免费.快速并且可靠的一种解决方案.HAProxy特别适用于那些负载特大的w

iOS:知识点简答

1.堆和栈什么区别? 答:管理方式:对于栈来讲,是由编译器自动管理,无需我们手工控制:对于堆来说,释放工作由程序员控制,容易产生memory leak. 2.数组和链表什么区别? 答:数组是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素. 链表恰好相反,链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起. 3.delegate和notification什么区别,什么情况使用? 答:Delegate:消息的发送者(sender)告知接收者(

mybatis返回list很智能很简答的,只需要配置resultmap进行类型转换,你dao方法直接写返回值list&lt;对应的object&gt;就行了啊

dao方法 public List<User> selectSimpleMulti(Map<String, Object> params){ if(params == null){ params = new HashMap<String, Object>(); } return dao.queryList(mapper+ "selectSimpleMulti", params); } 对应的mapper.xml配置sql语句 <resultMa

在GROUP BY中的做文章(一道题五中简答方法!)

被废话,直接上代码 测试代码,数据如下: CREATE TABLE #T( TIMES VARCHAR(15), RESULT NVARCHAR(20) ) INSERT INTO #T SELECT '2005-05-09','胜' UNION ALL SELECT '2005-05-09', '胜' UNION ALL SELECT '2005-05-09', '负' UNION ALL SELECT '2005-05-09', '负' UNION ALL SELECT '2005-05-1

S2T40,第四章,简答4

1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading.Tasks; 6 7 namespace Emmet 8 { 9 class emmet 10 { 11 public emmet(string name) 12 { 13 this.Name = name; 14 } 15 16 public string N

S2T40,第四章,简答5

1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading.Tasks; 6 7 namespace Emmet 8 { 9 class Wizard 10 { 11 public Wizard() 12 { 13 this.HP = 1000; 14 } 15 16 public Wizard(int level, i