在 java 中创建通用链表-ag捕鱼王app官网

本文我们将介绍如何在 java 中创建一个通用的单链表。

java linkedlist 简介

linkedlist 是线性数据结构，它将数据存储在随机地址的节点中，并且意味着位于不连续的位置。

每个节点都有两部分：数据和引用（地址）。 data/value字段存储值，reference字段存储链表的下一个节点的地址。

将作为成员函数实现的该数据结构的一些常见操作如下。

• addnode() - 此方法用于在 linkedlist 末尾添加新元素。
• removenode(value) - 此方法删除具有指定值的节点。
• addnode(position,value) - 此方法用于在特定位置添加值。
• clear() - 此方法清除整个 linkedlist。
• isempty() - 此方法用于检查 linkedlist 是否为空。
• length() - 此方法为我们提供 linkedlist 的长度。

java中单链表的通用实现

普通的linkedlist只能存储一种类型的值：整型、字符串、布尔型、浮点型等，所以我们在创建的时候就必须指定类型，但是如果我们要创建一个可以存储任意类型数据的linkedlist怎么办？ 数据类型; 为此，我们将使用 java 中的泛型概念。

创建通用节点类：

在下面的代码中，t表示linkedlist上存储的数据类型。

class node
{
    t value;
    node nextptr;
    node(t value)
    {
        this.value = value;
        this.nextptr = null;
    }
}

现在让我们创建通用 linkedlist 类创建方法。

1. add() 函数：

   void add(t value)
   {
    node temp = new node<>(value);  //creating a new node
    if(this.head == null)   //checking if the list is empty
        head = temp;
    else             //if the list is not empty, we go till the end and add the node
    {
        node tr = head;
        while(tr.nextptr!=null){
            tr = tr.nextptr;
        }
        tr.nextptr = temp;
    }
    length = length   1;  //increasing the length of list
   }
   

2. remove() 函数:

   void remove(t key)
   {
    node prev = new node<>(null);
    prev.nextptr = head;
    node next = head.nextptr;
    node tr = head;
    boolean isnodepresent = false; // to check if node is present
    if(head.value == key ){
        head = head.nextptr;
        isnodepresent =true;
    }
    while(tr.nextptr!=null)
    {
        if(string.valueof(tr.value).equals(string.valueof(key))){  //if the node is present, we break the loop
            prev.nextptr = next;  //we assign previous node's nextptr to next node
            isnodepresent = true;
            break;
        }
        prev = tr;   //updating the previous and next pointers
        tr = tr.nextptr;
        next = tr.nextptr;
    }
    if(isnodepresent==false && string.valueof(tr.value).equals(string.valueof(key))){
        prev.nextptr = null;
        isnodepresent = true;
    }
    if(isnodepresent)
    {
        length--;   //if the node is present, we reduce the length
    }
    else
    {
        system.out.println("the value is not present inside the linkedlist");
    }
   }
   

3. add(position,value) 函数:

   void add(int position,t value)
   {
    if(position>length 1)   //if the position entered is more than the list length
    {
        system.out.println("position out of bound");
        return;
    }
    if(position==1){             //if the position is one we'll just
        node temp = head;
        head = new node(value);
        head.nextptr = temp;
        return;
    }
    node tr = head;
    node prev = new node(null);   //creating a new node prev
    while(position-1>0)  //we find the position in the list
    {
        prev = tr;
        tr = tr.nextptr;
        position--;
    }
    prev.nextptr = new node(value);  //update the next pointer of previous node
    prev.nextptr.nextptr = tr;
   }
   

4. getlength() 函数:

   int getlength()
   {
    return this.length;  //returns the length of the list
   }
   

5. isempty() 函数:

   boolean isempty()
   {
    if(head == null)  //if the list is empty we return true
        return true;
    else
        return false;
   }
   

6. clear() 函数:

   void clear()
    {
        head = null;  //make head as null and length as zero
        length = 0;
    }
   

7. tostring() 函数: 在下面的代码中，我们添加并重写了 tostring 方法来打印 linkedlist 的内容。

   @override
   public string tostring()
   {
   node temp = head;
   string str = "{ ";
   if(temp == null)  //if the list is empty
   {
      system.out.println( "list is empty");
   }
   while(temp.nextptr!=null) //we keep appending data to string till the list is empty
   {
      str  = string.valueof(temp.value)  "->";
      temp = temp.nextptr;
   }
   str  = string.valueof(temp.value);
   return str "}";           //we finally return the string
   }
   

带有主类的完整工作代码：

class node
{
    t value;
    node nextptr;
    node(t value)
    {
        this.value = value;
        this.nextptr = null;
    }
}
class linkedlist
{
    node head;
    private int length = 0;
    linkedlist()
    {
        this.head = null;
    }
    void add(t value)
    {
        node temp = new node<>(value);
        if(this.head == null)
            head = temp;
        else
        {
            node tr = head;
            while(tr.nextptr!=null){
                tr = tr.nextptr;
            }
            tr.nextptr = temp;
        }
        length = length   1;
    }
    void remove(t key)
    {
        node prev = new node<>(null);
        prev.nextptr = head;
        node next = head.nextptr;
        node tr = head;
        boolean isnodepresent = false;
        if(head.value == key ){
            head = head.nextptr;
            isnodepresent =true;
        }
        while(tr.nextptr!=null)
        {
            if(string.valueof(tr.value).equals(string.valueof(key))){
                prev.nextptr = next;
                isnodepresent = true;
                break;
            }
            prev = tr;
            tr = tr.nextptr;
            next = tr.nextptr;
        }
        if(isnodepresent==false && string.valueof(tr.value).equals(string.valueof(key))){
            prev.nextptr = null;
            isnodepresent = true;
        }
        if(isnodepresent)
        {
            length--;
        }
        else
        {
            system.out.println("the value is not present inside the linkedlist");
        }
    }
    void add(int position,t value)
    {
        if(position>length 1)
        {
            system.out.println("position out of bound");
            return;
        }
        if(position==1){
            node temp = head;
            head = new node(value);
            head.nextptr = temp;
            return;
        }
        node tr = head;
        node prev = new node(null);
        while(position-1>0)
        {
            prev = tr;
            tr = tr.nextptr;
            position--;
        }
        prev.nextptr = new node(value);
        prev.nextptr.nextptr = tr;
    }
    int getlength()
    {
        return this.length;
    }
    boolean isempty()
    {
        if(head == null)
            return true;
        else
            return   false;
    }
    void clear()
    {
        head = null;
        length = 0;
    }
    @override
     public string tostring()
    {
      node temp = head;
      string str = "{ ";
      if(temp == null)
      {
          system.out.println( "list is empty");
      }
      while(temp.nextptr!=null)
      {
          str  = string.valueof(temp.value)  "->";
          temp = temp.nextptr;
      }
      str  = string.valueof(temp.value);
      return str "}";
    }
}
public class example
{
    public static void main(string[] args) {
       linkedlist ll = new linkedlist<>();
       ll.add(1);
       ll.add(2);
       ll.add(3);
       system.out.println(ll);
       ll.remove(3);
       system.out.println(ll);
       ll.add(2,800);
       system.out.println(ll);
    }
}

输出:

{ 1->2->3}
{ 1->2}
{ 1->800->2}