你的位置:首页 > Java教程

[Java教程]用java实现单链表 双向链表


package code;class Node{  Node next;  int data;  public Node(int data)  {    this.data=data;  }  }class LinkList{  Node first;  //头部  public LinkList()  {    this.first=null;  }  public void addNode(Node no)  {    no.next=first;    first=no;//在头部添加  }  public void delectNode()  {    Node n=first.next;    first=null;    first=n;//在头部删除  }  //删除指定位置  public int Number()  {    int count=1;    //查看有多少元素    Node nd=first;    while(nd.next!=null)    {      nd=nd.next;      count++;    }    return count;  }  public void delectExact(int n)  {    //删除指定位置    if(n>1)    {      int count=1;      Node de=first;      while(count<n-1)      {        de=de.next;        count++;              }      de.next=de.next.next;    }    else      first=first.next;      }  public void addExact(int n,Node nd)  {    if(n>1)//添加指定位置    {      int count=1;      Node de=first;      while(count<n-1)      {        de=de.next;        count++;              }      nd.next=de.next;      de.next=nd;    }    else      first=first.next;  }  public int findNode(int n)  {    int count=1;//查找一个数对应的位置    Node de=first;    while(de.data!=n)    {      de=de.next;      count++;      if(de==null)      {        return -1;      }    }    return count;  }  public void print()  {    Node no=first;//打印所有    while(no!=null)    {      System.out.println(no.data);      no=no.next;    }  }}public class TextNode{  public static void main(String[] args)  {    LinkList ll=new LinkList();    ll.addNode(new Node(12));    ll.addNode(new Node(15));    ll.addNode(new Node(18));    ll.addNode(new Node(19));    ll.addNode(new Node(20));    /*System.out.println(ll.first.data);    ll.delectNode();    System.out.println(ll.first.data);*/    System.out.println(ll.Number());    ll.delectExact(3);    ll.addExact(3, new Node(100));    System.out.println(ll.Number());//    ll.print();    System.out.println(ll.findNode(112));      }}

下面为双向链表

public class DoubleLink{  public static void main(String[]args)  {    Node2 no=new Node2(5);    no.addLeft(new Node2(6));    no.addRight(new Node2(7));    /*no.print();    no.print2();*/    no.addExact2(1, new Node2(8));    no.print();    System.out.println("--------------");    no.print2();  }}class Node2{  public Node2 first;  public Node2 end;  public Node2 left;  public Node2 right;  int data=0;  public Node2(int n)  {        first=this;    end=this;        first.data=n;  }  //从头部添加  public void addLeft(Node2 before)  {    first.left=before;    before.right=first;    first=before;  }  //从尾部添加  public void addRight(Node2 after)  {    end.right=after;    after.left=end;    end=after;  }  //插入正数(第三声)的第几个  public void addExact(int n,Node2 no)  {    int count=0;    if(n==0)    {      addLeft(no);    }    else    {        Node2 f=first;      while(true)      {        f=f.right;        count++;        if(count==n)        {          //此处为四个指针的指向的变化          no.left=f.left;          f.left.right=no;  //        first.left=no;          no.right=f;          f.left=no;          break;        }        }    }  }  //插入倒数的第几个  public void addExact2(int n,Node2 no)  {    int count=0;    if(n==0)    {      addRight(no);    }    else    {      Node2 f=end;      while(true)      {        f=f.left;        count++;        if(count==n)        {                    no.left=f;          no.right=f.right;          f.right.left=no;          f.right=no;          break;                  }      }    }  }  //正序遍历  public void print()  {    System.out.println(first.data);    while(first.right!=null)    {      System.out.println(first.right.data);      first=first.right;    }//    System.out.println(end.data);  }  //倒序遍历  public void print2()  {    System.out.println(end.data);    while(end.left!=null)    {      System.out.println(end.left.data);      end=end.left;    }  }  }/*值得注意的是,每一次插入一个新的对象的时候,需要注意指针指向的改变。首先是这个新的对象两边的指向(左和右),其次是时左边的对象向右的指向和右边对象向左的指向。这四个指针的指向必须正确,否则可能导致正序或者倒序遍历无法实现。*//*对比单链表,单链表只能从一个方向遍历,因为只有一个头,而双向链表,有头和尾,可以从 * 头遍历,也可以从尾遍历,而且其中一个对象因为有两个方向的指针,所以他可以获得左边的 * 对象也可以获得右边的对象。 * 但是单链表的话,因为只有一个方向,所以只能向左或右。添加对象的时候,双向也可以从头添加,也可以从尾添加。 * 如果单链表要实现两个方向添加比较难得,或者说不行,因为他只有向左或向右的一个方向的指针 * 而双向链表每个对象都有两个方向的指针没这样更灵活,但是这同样有缺点,因为这样的话每个对象 * 都会包含两个指针,这同样内存会消耗更多。 * * */

 

 

 

大一菜鸟初学,有误之处请谅解。