单链表实现

2021年09月15日 阅读数:1
这篇文章主要向大家介绍单链表实现,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

//Node类 java

public class Node  node

{  ide

 public int i; 测试

 public Node next;排序

}接口

//single接口 rem

public interface Singly extends java.io.Serializable it

{  //下标值计数都是从0开始io

 public void add(int i); //在链表末端追加一个节点class

 public void add(int index, int i); //在index位置插入一个节点

 public void remove(int index);  //删除位置为index的节点

 public boolean contains(int i); //判断链表中是否包含数据i

 public void clear();  //清空全部节点

 public int size();   //返回单链表大小

 public Singly subSingly(int from, int to);  //返回单链表中一部分节点数据,包含                                  

                                               from位置的节点数据,不包含to位置

                                      的节点数据,返回的单链表的长度是to - from.

 public void sort();   //排序

 public intavg();     //求链表中全部节点的平均值

 public String toString(); //输出链表中全部节点的值,使用, 做为分隔符。最后一个节

                             点的使用。做为结束符。

 }


//single的实现

import java.io.*;  

public class MySingly implements Singly

{

 Node head;

 Node tail;

 int Size=0;

 public void add(int i)//在链表末端追加一个节点

 {

   Node addnode=new Node();

  addnode.i=i;

  if(Size==0)

  {  

    head=addnode;

    tail=addnode;

  }

  else

  {

    tail.next=addnode;

    tail=addnode;

   }

  Size++;

}


public void add(int index, int i) //在index位置插入一个节点

 {

  Node addnode=new Node();

  addnode.i=i;

  Node temp=new Node();

  temp=head;

  for(int k=0;k<index-1;k++)

  {

   temp=temp.next;

  }

  addnode.next=temp.next;

  temp.next=addnode;

  Size++;

 }


public void remove(int index)  //删除位置为index的节点

 {

  Node temp=new Node();

  temp=head;

  for(int k=0;k<index;k++)

  {

  temp=temp.next;

  }

  temp.next=temp.next.next;

  Size--;

 }


public boolean contains(int i) //判断链表中是否包含数据i

 {

 Node current=new Node();

  current=head;

  for(int k=0;k<Size-1;k++)

  {

    if(current.i==i)  

    {

       return true;

    }

    else

    current=current.next;

  }

 return false;

}


public void clear() //清空全部节点

 {

  head=null;

  tail=null;

  Size=0;

 }


public int size()   //返回单链表大小

 {

  return Size;

 }


public Singly subSingly(int from, int to) //返回单链表中一部分节点数据,包含from

                                           位置的节点数据,

 {            //不包含to位置的节点数据,返回的单链表的长度是to - from.

  Singly subS=new MySingly();

  Node temp=new Node();

  temp=head;

  int j;

  for(j=0;j<from;j++)

  {

  temp=temp.next;

  }  

  for(int k=from;k<to;k++)

 {

   subS.add(temp.i);  

   temp=temp.next;

  }

 return subS;

 }

   

public void sort()  //排序

 {

  Node p, q;

  int temp;

  for(p=head; p.next!=null; p=p.next)

  {

   for(q=head; q.next!=null; q=q.next)

   {

   if(q.i>q.next.i)

   {

    temp=q.i;

     q.i=q.next.i;

     q.next.i=temp;

    }

  }

 }

}


public intavg()     //求链表中全部节点的平均值

{

  int sum=0;

  Node temp=new Node();

  temp=head;

  for(int k=0;k<Size;k++)

  {

   sum=sum+temp.i;

   temp=temp.next;

   }

  return (sum/Size);

  }


public String toString() //输出链表中全部节点的值,使用, 做为分隔符。最后一个节点

                        的使用。做为结束符。

 {

 String s=("");  

 Node temp=new Node();

  temp=head;

 for(int k=0;k<Size-1;k++)

  {  

  s=s+temp.i+',';

   temp=temp.next;

   }  

 s=s+temp.i;

 return s;

 }

}



//测试类

import java.io.*;  

public class Test

{

public static void main(String[] args)

  {

  Singly s = new MySingly();

  Test t = new Test();

  t.test(s);

   //Singly s2 = new RemoteSingly(host, port);

  //t.test(s2);

 }

 public void test(Singly s)

  {

  s.add(5);

  s.add(1);

  s.add(12);

  s.add(5);

  s.add(19);

  s.add(-1);

  s.add(3,8);

  System.out.println(s);

  System.out.println(s.avg());

  System.out.println(s.size());

  s.sort();

  System.out.println(s);

  s.remove(2);

  System.out.println(s);

  Singly s3 = s.subSingly(2,4);

   System.out.println(s3);

  if(s3.contains(5))

   System.out.println("Yes");

  else

  System.out.println("No");

  s3.clear();

  //System.out.println(s3);

  }

}