Heim  >  Artikel  >  Java  >  Java implementiert einfach verknüpfte Listen und doppelt verknüpfte Listen

Java implementiert einfach verknüpfte Listen und doppelt verknüpfte Listen

高洛峰
高洛峰Original
2017-01-24 16:19:571674Durchsuche

Die Beispiele in diesem Artikel teilen Ihnen die relevanten Codes für die Implementierung einfach verknüpfter Listen und doppelt verknüpfter Listen in Java als Referenz mit. Der spezifische Inhalt ist wie folgt

Java implementiert einfach verknüpfte Listen:

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));
   
 }
}

Java implementiert eine bidirektionale verknüpfte Liste:

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;
  }
 }
  
 
}
/*值得注意的是,每一次插入一个新的对象的时候,需要注意指针指向的改变。
首先是这个新的对象两边的指向(左和右),其次是时左边的对象向右的指向
和右边对象向左的指向。
这四个指针的指向必须正确,否则可能导致正序或者倒序遍历无法实现。
*/
/*对比单链表,单链表只能从一个方向遍历,因为只有一个头,而双向链表,有头和尾,可以从
 * 头遍历,也可以从尾遍历,而且其中一个对象因为有两个方向的指针,所以他可以获得左边的
 * 对象也可以获得右边的对象。
 * 但是单链表的话,因为只有一个方向,所以只能向左或右。添加对象的时候,双向也可以从头添加,也可以从尾添加。
 * 如果单链表要实现两个方向添加比较难得,或者说不行,因为他只有向左或向右的一个方向的指针
 * 而双向链表每个对象都有两个方向的指针没这样更灵活,但是这同样有缺点,因为这样的话每个对象
 * 都会包含两个指针,这同样内存会消耗更多。
 * 
 * */

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, dass er für alle beim Erlernen der Java-Programmierung hilfreich ist.

Weitere Artikel zur Java-Implementierung einfach verknüpfter Listen und doppelt verknüpfter Listen finden Sie auf der chinesischen PHP-Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn