双链表---LinkedList的重写
2024-10-19 21:22:55
重写Linkedlist类，改写为MyLinkedList,未继承Iterable类。
public class MyLinkedList<AnyType> {
private int theSize;
private Node<AnyType> beginMarker;
private Node<AnyType> endMarker;
private static class Node<AnyType>{ //定义匿名类Node
public Node(AnyType d,Node<AnyType> p,Node<AnyType> n){
this.data=d;
this.prev=p;
this.next=n;
}
public AnyType data;
public Node<AnyType> prev;
public Node<AnyType> next;
}
public MyLinkedList(){ //构造方法
beginMarker=new Node<AnyType>(null,null,null);
endMarker=new Node<AnyType>(null,beginMarker,null);
beginMarker.next=endMarker;
theSize=0;
}
public int size(){ //单链表cdu
return theSize;
}
public boolean isEmploy(){ //判断长度
return size()==0;
}
public Node<AnyType> getNode(int idx){ //返回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;
}
public AnyType get(int idx){ //返回idx位置的数据
return getNode(idx).data;
}
public AnyType set(int idx,AnyType newVal){
Node<AnyType> p=getNode(idx);
AnyType oldVal=get(idx);
p.data=newVal;
return oldVal;
}
public boolean add(AnyType x){ //插入元素
add(size(),x);
return true;
}
private void addBefore(Node<AnyType> p,AnyType x){
Node<AnyType> newNode=new Node<AnyType>(x,p.prev,p);
newNode.prev.next=newNode;
p.prev=newNode;
theSize++;
}
public void add(int idx,AnyType x){
Node<AnyType> p;
p=getNode(idx);
addBefore(p,x);
}
public AnyType remove(int idx){ //删除元素
return remove(getNode(idx));
}
public AnyType remove(Node<AnyType> p){
p.next.prev=p.prev;
p.prev.next=p.next;
theSize--;
return p.data;
}
public static void main(String[] args) {
//验证部分
MyLinkedList<String> La=new MyLinkedList<String>();
La.add("aaa");
La.add("bbb");
La.add("ccc");
La.add("ddd");
La.add("eee");
for(int i=0;i<La.size();i++){
System.out.println(i+": "+La.getNode(i).data);
}
System.out.println("......................");
La.add(2,"fff");
La.remove(0);
La.set(4,"ggg");
for(int i=0;i<La.size();i++){
System.out.println(i+": "+La.get(i));
}
}
}
最新文章
- 《征服 C 指针》摘录3：数组 与 指针
- 将光标放到input内容的最后
- VS2012添加PlaySound引用
- 水流雨渍shader
- JMeter性能测试介绍学习一
- Zabbix实现告警分级
- WP布局之Pivot和Panorama
- 今天分享一个抽奖的类Lottery
- C# PLINQ 内存列表查询优化历程
- Git教程(10)git比较复杂的功能
- getchar()与EOF
- Linux发展历史大事编年表（截止2013年）
- jQuery API 中文文档
- OC实现单选和多选按钮
- linux子系统折腾记 （二）
- hook NtTerminateProcess进行应用的保护
- java求解第N个素数(质数)
- Java分割ID和姓名（String不能当输出参数）
- Python作业第一课
- 使用exundelete在Linux下恢复删除的文件