黑马程序员技术交流社区

标题: 刚学完集合，尝试写了下LinkedList集合，求指正 [打印本页]

作者: gracefulwind 时间: 2015-11-24 22:29
标题: 刚学完集合，尝试写了下LinkedList集合，求指正
LinkedList代码底层就是利用了双向链表。
我尝试着自己写了一个，是跟着课程边学边写的。所以有些功能写的不好，比如get(index)方法和remove(index)方法没判它的长度是否该从尾部查起，
getfirst和getlast等功能也还没加入，等有空我完善了再和大家分享一次。
//----------------------链表的实现代码如下---------------------------
/要实现的内容
//1,前后节点
//2,size
//3,首尾地址属性
//4,单参的延生链表
//5，search，replace，delete，
//6,
public class Node<E> {
//private int num; //
private int size; //链表长度
private Node<E> firstNode; //首节点
private Node<E> lastNode; //末节点

private Node<E> nextNode = null; //后节点
private Node<E> preNode = null; //前节点
private E /*Object*/ obj; //存储的内容

public Node() {
super();
size = 0;
firstNode = this;
}

public Node(E anobject) {
super();
//Node newNode = new Node();
this.obj = anobject;
}

public int size(){
return size;
}

//实现，在链表末尾插入新值,注意表头为this.nextNode,this为调用对象其索引为-1
/* public boolean add(Object anobject){
Node newNode =new Node(anobject);
incNode(this,newNode);//这段需要重写已过时。可用
size++;
if(firstNode == null)
firstNode = newNode;
lastNode = newNode;
return true;
}*/

//测试firstNode和lastNode用代码，需删除
public Object getFirst(){
return firstNode.obj;
}
public Object getlast(){
return lastNode.obj;
}
//测试已通过，可删除

//根据聊表尾地址增长链表
public boolean add(E anobject){
Node<E> newNode =new Node<E>(anobject);
incNode(this,newNode);
if(size == 0){
firstNode = newNode;
lastNode = newNode;
this.nextNode = newNode;
newNode.preNode = this;
}
else{
lastNode.nextNode = newNode;
newNode.preNode = lastNode;
lastNode = newNode;
}
size++;
return true;
}
//实现,在指定位置插入对象功能
public boolean add(int index,E anobject){
if(index > size &&index <0)
return false;
Node<E> newNode =new Node<E>(anobject);
if(size == 0){
firstNode = newNode;
lastNode = newNode;
this.nextNode = newNode;
newNode.preNode = this;
}
if(index == 0)
firstNode = newNode;
if(index == size)
lastNode = newNode;
Node<E> targetNode = searchIndex(index,this);//从对象名后面开始插值，此时获得的目标为索引-1
if(targetNode.nextNode != null ){
newNode.preNode = targetNode;
newNode.nextNode = targetNode.nextNode;
targetNode.nextNode = newNode;
newNode.nextNode.preNode = newNode;
}else{
newNode.preNode = targetNode;
//newNode.nextNode = targetNode.nextNode;//null=null,所以此句无用
targetNode.nextNode = newNode;
}
size++;
return true;
}

//已实现，删除指定索引的链表节点
public boolean remove(int index){
if(index >= size && index <0)
return false;
size--;
if(index == 0)
firstNode = firstNode.nextNode;
if(index == size)
lastNode = lastNode.preNode;
//此时不可能取到索引末尾，取得的最后地址为(索引-1),targetNode_1为目标节点前一个节点
Node<E> targetNode_1 = searchIndex(index,this);
if(targetNode_1.nextNode.nextNode != null){
targetNode_1.nextNode.nextNode.preNode = targetNode_1;
targetNode_1.nextNode = targetNode_1.nextNode.nextNode;
// Node tempNode = targetNode_1.nextNode.nextNode;
// targetNode_1.nextNode = tempNode;
return true;
}else{
targetNode_1.nextNode = null;
return true;
}
}
//已实现，删除指定元素的链表节点，调用toString属性判断二者是否相等，正确删除返回true，找不到返回false
public boolean remove(E anobject){
Node<E> targetNode = searchObject(anobject,this.nextNode);
if(targetNode == null){
return false;
}else if(targetNode.nextNode == null){
targetNode.preNode.nextNode = null;
lastNode = targetNode.preNode;
return true;
}else{
if(targetNode == firstNode)
firstNode = targetNode.nextNode;
targetNode.nextNode.preNode = targetNode.preNode;
targetNode.preNode.nextNode = targetNode.nextNode;
return true;
}
}

//已实现，返回指定索引的Object属性
public E get(int index){
//若是索引越界，返回null
if(index >= size && index <0)
return null;
Node<E> targetNode = searchIndex(index,this.nextNode);
return targetNode.obj;
}
//由于toString方法已经重写，所以该方法可以放弃，但其显示效率比toString高
public void show(){
if(this.nextNode == null)
return;
System.out.print("[");
showNode(this.nextNode);
}

@Override
public String toString() {
if(this.nextNode == null)
return null;
String str = new String();
str += "[";
str = nodeToString(this.nextNode,str);
return str;
}

//--------------------------------------
//在x1最后新插入Node，延长链表，靠add方法调用
private void incNode(Node<E> x1,Node<E> x2)
{
if(x1.nextNode == null)
{
x2.nextNode = null;
x2.preNode = x1;
x1.nextNode = x2;
}else
{
incNode(x1.nextNode,x2);
}
}

//已实现，递归寻找指定索引的地址
private Node<E> searchIndex(int index,Node<E> nowNode){
Node<E> returnNode = null;
if (index == 0){
return (returnNode = nowNode);
}
else {
index--;
returnNode = searchIndex(index,nowNode.nextNode);
}
return returnNode;
}
//未实现，重复功能函数，放弃使用
/* private  void nodeInsert(int index,Node newNode){
Node returnNode = null;
if (index ==0){
return (returnNode = nowNode);
}
else {
index--;
returnNode = searchNode(index,nowNode.nextNode);
}
return returnNode;
}*/
private Node<E> searchObject(E tarObject,Node<E> nowNode){
Node<E> targetNode = null;
if(tarObject.equals(nowNode.obj)){
return nowNode;
}else if(nowNode.nextNode == null){
return null;
}else{
targetNode = searchObject(tarObject,nowNode.nextNode);
}
return targetNode;
}

//遍历显示链表的所有属性
private void showNode(Node<E> nowNode)
{
System.out.print(nowNode.obj.toString());
if(nowNode.nextNode == null)
{
System.out.println("]");
}else
{
System.out.print(",");
showNode(nowNode.nextNode);
}
}
private String nodeToString(Node<E> nowNode, String str) {
String str1=str + nowNode.obj.toString();
if(nowNode.nextNode == null)
{
str1 += "]";
}else
{
str1 += ",";
str1 = nodeToString(nowNode.nextNode,str1);
}
return str1;
}
}

//------------下面是主程序里的演示模块，其实用起来和系统自带的LinkedList一样啦。当然功能没他那么强大，不过泛型之类的已经实现了。有建议的可以联系我，我学习空隙改下，谢谢。
public static void main(String[] args) {
/*
   * Node的add、add带索引、remove索引、remove指定object、get函数、size函数、以及
      显示结果函数均已经实现*/
Node c = new Node();//Linklist c = new Linklist();
c.add("a");
c.add("b");
c.add("c");
c.add("123");
//将"23"插在0位置
c.add(0, "23");
c.add(5,100);
c.add(5,101);
//删除第一个以及最后一个元素
c.remove(0);
c.remove(c.size()-1);
//新建学生类对象
c.add(new Student());
//删除"23"元素
c.remove("23");
//已实现toString,c.show方法可以隐藏
c.show();
System.out.println(c);
System.out.println(c.get(2).toString());

//-----------------------------------------------------------
源码的java文件我已经发在附件里了，方便大家测试使用