使用 Java 的 DSA - 快速指南

使用 Java 的 DSA - 概述

什么是数据结构？

数据结构是一种组织数据以使其能够有效使用的方法。以下术语是数据结构的基础术语。

接口- 每个数据结构都有一个接口。接口代表数据结构支持的操作集。接口仅提供支持的操作列表、它们可以接受的参数类型以及这些操作的返回类型。
实现- 实现提供数据结构的内部表示。实现还提供了数据结构操作中使用的算法的定义。

数据结构的特征

正确性- 数据结构实现应该正确实现其接口。
时间复杂度- 数据结构操作的运行时间或执行时间必须尽可能小。
空间复杂度- 数据结构操作的内存使用量应尽可能少。

对数据结构的需求

随着应用程序变得越来越复杂且数据越来越丰富，应用程序现在面临三个常见问题。

数据搜索- 考虑商店的100 万（10 ⁶ ）件商品的库存。如果应用程序是搜索一个项目。每次它必须搜索 100 万（10 ^{6 ）个项目，这会减慢搜索速度。}随着数据的增长，搜索会变得更慢。
处理器速度- 虽然处理器速度非常高，但如果数据增长到数十亿条记录，处理器速度就会受到限制。
多个请求- 由于数千个用户可以在 Web 服务器上同时搜索数据，因此即使非常快的服务器在搜索数据时也会失败。

为了解决上述问题，数据结构就派上用场了。数据可以以这样的方式组织在数据结构中：不需要搜索所有项目并且几乎可以立即搜索所需的数据。

执行时间案例

通常使用三种情况以相对方式比较各种数据结构的执行时间。

最坏情况- 这是特定数据结构操作花费最大时间的情况。如果操作的最坏情况时间为 f(n)，则该操作所花费的时间不会超过 f(n) 时间，其中 f(n) 表示 n 的函数。
平均情况- 这是描述数据结构操作的平均执行时间的场景。如果执行一个操作需要 f(n) 时间，则 m 个操作将花费 mf(n) 时间。
最佳情况- 这是描述数据结构操作的最短可能执行时间的场景。如果一个操作在执行中需要 f(n) 时间，那么实际操作可能会花费随机数的时间，该时间最大为 f(n)。

使用 Java 的 DSA - 环境设置

本地环境设置

如果您仍然愿意为 Java 编程语言设置环境，那么本节将指导您如何在计算机上下载和设置 Java。请按照以下步骤设置环境。

Java SE 可以通过下载 Java链接免费获得。因此，您可以根据您的操作系统下载一个版本。

按照说明下载 java 并运行 .exe以在您的计算机上安装 Java。在计算机上安装 Java 后，您需要设置环境变量以指向正确的安装目录：

设置 Windows 2000/XP 的路径

假设您已将 Java 安装在c:\Program Files\java\jdk目录中：

右键单击“我的电脑”并选择“属性”。
单击“高级”选项卡下的“环境变量”按钮。
现在更改“Path”变量，使其也包含 Java 可执行文件的路径。例如，如果路径当前设置为“C:\WINDOWS\SYSTEM32”，则将路径更改为“C:\WINDOWS\SYSTEM32;c:\Program Files\java\jdk\bin”。

设置Windows 95/98/ME的路径

假设您已将 Java 安装在c:\Program Files\java\jdk目录中 -

编辑“C:\autoexec.bat”文件并在末尾添加以下行：
'SET PATH=%PATH%;C:\Program Files\java\jdk\bin'

设置 Linux、UNIX、Solaris、FreeBSD 的路径：

环境变量 PATH 应设置为指向 java 二进制文件的安装位置。如果您在执行此操作时遇到问题，请参阅您的 shell 文档。

例如，如果您使用bash作为 shell，那么您可以将以下行添加到 '.bashrc:export PATH=/path/to/java:$PATH' 的末尾

流行的 Java 编辑器

要编写 Java 程序，您需要一个文本编辑器。市场上还有更复杂的 IDE。但目前，您可以考虑以下其中一项：

记事本 -在 Windows 计算机上，您可以使用任何简单的文本编辑器，例如记事本（本教程推荐）、TextPad。
Netbeans -是一个开源且免费的 Java IDE，可以从https://www.netbeans.org/index.html下载。
Eclipse -也是由 eclipse 开源社区开发的 java IDE，可以从https://www.eclipse.org/下载。

下一步是什么？

下一章将教你如何编写和运行你的第一个java程序以及开发应用程序所需的一些重要的java基本语法。

使用 Java 的 DSA - 算法

算法概念

算法是一个逐步的过程，它定义了一组按一定顺序执行以获得所需输出的指令。在数据结构方面，算法的类别如下。

搜索- 搜索数据结构中的项目的算法。
排序- 按特定顺序对项目进行排序的算法
插入- 在数据结构中插入项目的算法
更新- 更新数据结构中现有项目的算法
删除- 从数据结构中删除现有项目的算法

算法分析

算法分析涉及数据结构的各种操作的执行时间或运行时间。操作的运行时间可以定义为否。每个操作执行的计算机指令的数量。由于任何操作的确切运行时间因一台计算机而异，因此我们通常将任何操作的运行时间分析为 n 的某个函数，其中 n 为编号。数据结构中该操作中处理的项目数。

渐近分析

渐近分析是指以数学计算单位计算任何操作的运行时间。例如，一个操作的运行时间计算为f (n)，另一操作的运行时间计算为g (n ² )。这意味着第一个操作的运行时间将随着n的增加而线性增加，而第二个操作的运行时间将随着n的增加而呈指数增加。类似地，如果 n 非常小，则两个操作的运行时间将几乎相同。

渐近符号

以下是计算算法运行时间复杂度时常用的渐近符号。

Ο 表示法
Ω 表示法
θ 表示法

大哦符号，Ο

Ο(n) 是表达算法运行时间上限的正式方式。它衡量最坏情况的时间复杂度或算法完成可能需要的最长时间。例如，对于函数f (n)

Ο( f (n)) = { g (n) ：存在 c > 0 且 n ₀使得g (n) ≤ c。f (n) 对于所有 n > n ₀。}

Big Oh 表示法用于简化函数。例如，我们可以将特定的函数方程 7nlogn + n - 1 替换为 Ο( f (nlogn))。考虑如下场景：

7nlogn +n - 1 ≤ 7nlogn + n

7nlogn +n - 1 ≤ 7nlogn + nlogn

当 n ≥ 2 时，logn ≥ 1

7nlogn +n - 1 ≤ 8nlogn

它表明，使用常数 c = 8 和 n _{0 = 2，}f (n) = 7nlogn + n - 1 在O (nlogn)的范围内。

欧米茄表示法，Ω

Ω(n) 是表达算法运行时间下限的正式方式。它衡量最佳情况的时间复杂度或算法完成可能需要的最佳时间。

例如，对于函数f (n)

Ω( f (n)) ≥ { g (n) ：存在 c > 0 且 n ₀使得g (n) ≤ c。f (n) 对于所有 n > n ₀。}

Theta 表示法，θ

θ(n) 是表达算法运行时间下限和上限的正式方式。其表示如下。

θ( f (n)) = { g (n) 当且仅当g (n) = Ο( f (n)) 且g (n) = Ω( f (n)) 对于所有 n > n ₀。}

使用 Java 的 DSA - 数据结构

数据结构是一种组织数据以使其能够有效使用的方法。以下术语是数据结构的基本术语。

数据定义

数据定义定义了具有以下特征的特定数据。

Atomics - 定义应该定义一个概念
可追踪- 定义应该能够映射到某些数据元素。
准确 - 定义应该明确。
清晰简洁- 定义应该是可以理解的。

数据对象

数据对象表示具有数据的对象。

数据类型

数据类型是对整数、字符串等各种类型的数据进行分类的方式，它决定了相应类型的数据可以使用的值、可以对相应类型的数据执行的操作类型。两种类型的数据类型 -

内置数据类型
派生数据类型

内置数据类型

语言内置支持的那些数据类型称为内置数据类型。例如，大多数语言都提供以下内置数据类型。

整数
布尔值（真、假）
浮点数（十进制数）
字符和字符串

派生数据类型

那些与实现无关的数据类型，因为它们可以以一种或其他方式实现，被称为派生数据类型。这些数据类型通常是通过主数据类型或内置数据类型及其关联操作的组合来构建的。例如 -

列表
大批
堆
队列

使用 Java 的 DSA - 数组

数组基础知识

数组是一个可以容纳固定数量的项目的容器，并且这些项目应该具有相同的类型。大多数数据结构都使用数组来实现其算法。以下是理解数组概念的重要术语

元素- 存储在数组中的每个项目称为元素。
索引- 数组中元素的每个位置都有一个数字索引，用于标识该元素。

数组表示

根据上图所示，以下是需要考虑的要点。

索引从0开始。
数组长度为8，这意味着它可以存储8个元素。
每个元素都可以通过其索引来访问。例如，我们可以将索引 6 处的元素获取为 9。

基本操作

以下是数组支持的基本操作。

插入- 在给定索引处添加一个元素。
删除- 删除给定索引处的元素。
搜索- 使用给定索引或按值搜索元素。
更新- 更新给定索引处的元素。

在java中，当用大小初始化数组时，它会按以下顺序为其元素分配默认值。

数据类型	默认值
字节	0
短的	0
整数	0
长的	0升
漂浮	0.0f
双倍的	0.0天
字符	'\u0000'
布尔值	错误的
目的	无效的

演示

package com.tutorialspoint.array;

public class ArrayDemo {
   public static void main(String[] args){
      
      // Declare an array 
      int intArray[];
	  
      // Initialize an array of 8 int
      // set aside memory of 8 int 
      intArray = new int[8];

      System.out.println("Array before adding data.");

      // Display elements of an array.
      display(intArray);     
         
      // Operation : Insertion 
      // Add elements in the array 
      for(int i = 0; i< intArray.length; i++)
      {
         // place value of i at index i. 
         System.out.println("Adding "+i+" at index "+i);
         intArray[i] = i;
      }         
      System.out.println();

      System.out.println("Array after adding data.");
      display(intArray);

      // Operation : Insertion 
      // Element at any location can be updated directly 
      int index = 5;
      intArray[index] = 10;
      
      System.out.println("Array after updating element at index " + index);
      display(intArray);

      // Operation : Search using index
      // Search an element using index.
      System.out.println("Data at index " + index + ": "+ intArray[index]);
	  
      // Operation : Search using value
      // Search an element using value.
      int value = 4;
      for(int i = 0; i< intArray.length; i++)
      {
         if(intArray[i] == value ){
            System.out.println(value + " Found at index "+i);
            break;
         }
      }         
      System.out.println("Data at index " + index + ": "+ intArray[index]);
   }

   private static void display(int[] intArray){
      System.out.print("Array : [");
      for(int i = 0; i< intArray.length; i++)
      {
         // display value of element at index i. 
         System.out.print(" "+intArray[i]);
      }
      System.out.println(" ]");
      System.out.println();
   }
}

如果我们编译并运行上面的程序，那么它将产生以下结果 -

Array before adding data.
Array : [ 0 0 0 0 0 0 0 0 ]

Adding 0 at index 0
Adding 1 at index 1
Adding 2 at index 2
Adding 3 at index 3
Adding 4 at index 4
Adding 5 at index 5
Adding 6 at index 6
Adding 7 at index 7

Array after adding data.
Array : [ 0 1 2 3 4 5 6 7 ]

Array after updating element at index 5
Array : [ 0 1 2 3 4 10 6 7 ]

Data at index 5: 10
4 Found at index: 4

使用 Java 的 DSA - 链表

链表基础知识

链接列表是包含项目的链接序列。每个链接都包含到另一个链接的连接。链表是继数组之后第二常用的数据结构。以下是理解链表概念的重要术语。

链接- 链表的每个链接都可以存储称为元素的数据。
Next - 链接列表的每个链接都包含一个指向下一个链接的链接，称为“Next”。
LinkedList - LinkedList 包含指向名为 First 的第一个链接的连接链接。

链表表示

根据上图所示，以下是需要考虑的要点。

LinkedList 包含一个名为first 的链接元素。
每个链接携带一个数据字段和一个接下来调用的链接字段。
每个链接都使用其下一个链接与其下一个链接进行链接。
Last Link 带有一个为 null 的 Link 来标记列表的结尾。

链表的类型

以下是链表的各种风格。

简单链接列表- 项目导航仅向前。
双向链表- 项目可以向前和向后导航。
循环链表- 最后一项包含第一个元素作为下一个元素的链接，第一个元素包含到最后一个元素作为上一个元素的链接。

基本操作

以下是列表支持的基本操作。

插入- 在列表的开头添加一个元素。
删除- 删除列表开头的元素。
显示- 显示完整列表。
搜索- 使用给定键搜索元素。
删除- 使用给定键删除元素。

插入操作

插入过程分为三个步骤：

使用提供的数据创建新链接。
将新链接指向旧的第一个链接。
将第一个链接指向此新链接。

//insert link at the first location
public void insertFirst(int key, int data){
   //create a link
   Link link = new Link(key,data);
   //point it to old first node
   link.next = first;
   //point first to new first node
   first = link;
}

删除操作

删除过程分为两步：

获取第一个链接指向的链接作为临时链接。
将第一个链接指向临时链接的下一个链接。

//delete first item
public Link deleteFirst(){
   //save reference to first link
   Link tempLink = first;
   //mark next to first link as first 
   first = first.next;
   //return the deleted link
   return tempLink;
}

导航操作

导航是一个递归步骤过程，是许多操作（如搜索、删除等）的基础：

获取第一个链接指向的链接作为当前链接。
检查当前链接是否不为空并显示它。
将当前链接指向当前链接的下一个链接并移至上述步骤。

笔记

//display the list
public void display(){
   //start from the beginning
   Link current = first;
   //navigate till the end of the list
   System.out.print("[ ");
   while(current != null){
      //print data
      current.display();
      //move to next item
      current = current.next;
      System.out.print(" ");
   }
   System.out.print(" ]");
}

高级操作

以下是为列表指定的高级操作。

排序- 根据特定顺序对列表进行排序。
反转- 反转链表。
连接- 连接两个列表。

排序操作

我们使用冒泡排序来对列表进行排序。

public void sort(){

   int i, j, k, tempKey, tempData ;
   Link current,next;
   int size = length();
   k = size ;
   for ( i = 0 ; i < size - 1 ; i++, k-- ) {
      current = first ;
      next = first.next ;
      for ( j = 1 ; j < k ; j++ ) {            
         if ( current.data > next.data ) {
            tempData = current.data ;
            current.data = next.data;
            next.data = tempData ;

            tempKey = current.key;
            current.key = next.key;
            next.key = tempKey;
         }
         current = current.next;
         next = next.next;                        
      }
   }
}

反向操作

以下代码演示了反转单个链表。

public LinkedList reverse() { 
   LinkedList reversedlist = new LinkedList();
   Link nextLink = null;     
   reversedlist.insertFirst(first.key, first.data);

   Link currentLink = first;       
   // Until no more data in list, 
   // insert current link before first and move ahead.
   while(currentLink.next != null){
      nextLink = currentLink.next;           
      // Insert at start of new list.
      reversedlist.insertFirst(nextLink.key, nextLink.data); 
      //advance to next node
      currentLink = currentLink.next;            
   }      
   return reversedlist;
}

连接操作

以下代码演示了反转单个链表。

public void concatenate(LinkedList list){
   if(first == null){
      first = list.first;
   }
   if(list.first == null){
      return;
   }
   Link temp = first;
   while(temp.next !=null) {
      temp = temp.next;
   }
   temp.next = list.first;       
}

演示

链接.java

package com.tutorialspoint.list;

public class Link {
   public int key;
   public int data;
   public Link next;

   public Link(int key, int data){
      this.key = key;
      this.data = data;
   }

   public void display(){
      System.out.print("{"+key+","+data+"}");
   }
}

链表.java

package com.tutorialspoint.list;

public class LinkedList {
   //this link always point to first Link 
   //in the Linked List 
   private Link first;

   // create an empty linked list 
   public LinkedList(){
      first = null;
   }

   //insert link at the first location
   public void insertFirst(int key, int data){
      //create a link
      Link link = new Link(key,data);
      //point it to old first node
      link.next = first;
      //point first to new first node
      first = link;
   }

   //delete first item
   public Link deleteFirst(){
      //save reference to first link
      Link tempLink = first;
      //mark next to first link as first 
      first = first.next;
      //return the deleted link
      return tempLink;
   }

   //display the list
   public void display(){
      //start from the beginning
      Link current = first;
      //navigate till the end of the list
      System.out.print("[ ");
      while(current != null){
         //print data
         current.display();
         //move to next item
         current = current.next;
         System.out.print(" ");
      }
      System.out.print(" ]");
   }

   //find a link with given key
   public Link find(int key){
      //start from the first link
      Link current = first;

      //if list is empty
      if(first == null){
         return null;
      }
      //navigate through list
      while(current.key != key){
         //if it is last node
         if(current.next == null){
            return null;
         }else{
            //go to next link
            current = current.next;
         }
      }      
      //if data found, return the current Link
      return current;
   }

   //delete a link with given key
   public Link delete(int key){
      //start from the first link
      Link current = first;
      Link previous = null;
      //if list is empty
      if(first == null){
         return null;
      }

      //navigate through list
      while(current.key != key){
         //if it is last node
         if(current.next == null){
            return null;
         }else{
            //store reference to current link
            previous = current;
            //move to next link
            current = current.next;             
         }
      }

      //found a match, update the link
      if(current == first) {
         //change first to point to next link
         first = first.next;
      }else {
         //bypass the current link
         previous.next = current.next;
      }    
      return current;
   }


   //is list empty
   public boolean isEmpty(){
      return first == null;
   }
   
   public int length(){
      int length = 0;
      for(Link current = first; current!=null;
         current = current.next){
         length++;
      }
      return length;
   }
   
   public void sort(){
      int i, j, k, tempKey, tempData ;
      Link current,next;
      int size = length();
      k = size ;
      for ( i = 0 ; i < size - 1 ; i++, k-- ) {
         current = first ;
         next = first.next ;
         for ( j = 1 ; j < k ; j++ ) {            
            if ( current.data > next.data ) {
               tempData = current.data ;
               current.data = next.data;
               next.data = tempData ;
	 
	           tempKey = current.key;
	           current.key = next.key;
	           next.key = tempKey;
            }
            current = current.next;
           next = next.next;                        
         }
      }
   }

   public LinkedList reverse() { 
      LinkedList reversedlist = new LinkedList();
      Link nextLink = null;     
      reversedlist.insertFirst(first.key, first.data);

      Link currentLink = first;       
      // Until no more data in list, 
      // insert current link before first and move ahead.
      while(currentLink.next != null){
         nextLink = currentLink.next;           
         // Insert at start of new list.
         reversedlist.insertFirst(nextLink.key, nextLink.data); 
         //advance to next node
         currentLink = currentLink.next;            
      }      
      return reversedlist;
   }

   public void concatenate(LinkedList list){
      if(first == null){
         first = list.first;
      }
      if(list.first == null){
         return;
      }
      Link temp = first;

      while(temp.next !=null) {
         temp = temp.next;
      }
      temp.next = list.first;       
   }
}

LinkedListDemo.java

package com.tutorialspoint.list;

public class LinkedListDemo {
   public static void main(String args[]){
      LinkedList list = new LinkedList();
        
      list.insertFirst(1, 10);
      list.insertFirst(2, 20);
      list.insertFirst(3, 30);
      list.insertFirst(4, 1);
      list.insertFirst(5, 40);
      list.insertFirst(6, 56);

      System.out.print("\nOriginal List: ");  
      list.display();
      System.out.println("");
      while(!list.isEmpty()){            
         Link temp = list.deleteFirst();
         System.out.print("Deleted value:");  
         temp.display();
         System.out.println("");
      }         
      System.out.print("List after deleting all items: ");          
      list.display();
      System.out.println("");
      list.insertFirst(1, 10);
      list.insertFirst(2, 20);
      list.insertFirst(3, 30);
      list.insertFirst(4, 1);
      list.insertFirst(5, 40);
      list.insertFirst(6, 56);

      System.out.print("Restored List: ");  
      list.display();
      System.out.println("");  

      Link foundLink = list.find(4);
      if(foundLink != null){
        System.out.print("Element found: ");  
         foundLink.display();
         System.out.println("");  
      }else{
         System.out.println("Element not found.");  
      }

      list.delete(4);
      System.out.print("List after deleting an item: ");  
      list.display();
      System.out.println(""); 
      foundLink = list.find(4);
      if(foundLink != null){
         System.out.print("Element found: ");  
         foundLink.display();
         System.out.println("");  
      }else{
         System.out.print("Element not found. {4,1}");  
      }
      System.out.println(""); 
      list.sort();
      System.out.print("List after sorting the data: ");  
      list.display();
      System.out.println(""); 
      System.out.print("Reverse of the list: ");  
      LinkedList list1 = list.reverse();
      list1.display();
      System.out.println(""); 
      
      LinkedList list2 = new LinkedList();

      list2.insertFirst(9, 50);
      list2.insertFirst(8, 40);
      list2.insertFirst(7, 20);

      list.concatenate(list2);
      System.out.print("List after concatenation: ");  
      list.display();
      System.out.println(""); 
   }
}

如果我们编译并运行上面的程序，那么它将产生以下结果：

Original List: [ {6,56} {5,40} {4,1} {3,30} {2,20} {1,10}  ]
Deleted value:{6,56}
Deleted value:{5,40}
Deleted value:{4,1}
Deleted value:{3,30}
Deleted value:{2,20}
Deleted value:{1,10}
List after deleting all items: [  ]
Restored List: [ {6,56} {5,40} {4,1} {3,30} {2,20} {1,10}  ]
Element found: {4,1}
List after deleting an item: [ {6,56} {5,40} {3,30} {2,20} {1,10}  ]
Element not found. {4,1}
List after sorting the data: [ {1,10} {2,20} {3,30} {5,40} {6,56}  ]
Reverse of the list: [ {6,56} {5,40} {3,30} {2,20} {1,10}  ]
List after concatenation: [ {1,10} {2,20} {3,30} {5,40} {6,56} {7,20} {8,40} {9,50}  ]

使用 Java 的 DSA - 双向链表

双向链表基础知识

双链表是链表的一种变体，与单链表相比，双链表可以轻松地向前和向后两种方式进行导航。以下是理解双向链表概念的重要术语

链接- 链表的每个链接都可以存储称为元素的数据。
Next - 链接列表的每个链接都包含一个指向下一个链接的链接，称为“Next”。
Prev - 链接列表的每个链接都包含一个指向称为 Prev 的上一个链接的链接。
LinkedList - LinkedList 包含指向名为 First 的第一个链接和名为 Last 的最后一个链接的连接链接。

双向链表表示

根据上图所示，以下是需要考虑的要点。

双向链表包含一个名为first 和last 的链接元素。
每个链接携带一个数据字段和一个接下来调用的链接字段。
每个链接都使用其下一个链接与其下一个链接进行链接。
每个链接都使用其上一个链接与其前一个链接进行链接。
Last Link 带有一个为 null 的 Link 来标记列表的结尾。

基本操作

以下是列表支持的基本操作。

插入- 在列表的开头添加一个元素。
删除- 删除列表开头的元素。
Insert Last - 在列表末尾添加一个元素。
删除最后一个- 从列表末尾删除一个元素。
Insert After - 在列表的项目之后添加一个元素。
删除- 使用 key 从列表中删除一个元素。
向前显示- 以向前方式显示完整列表。
向后显示- 以向后方式显示完整列表。

插入操作

以下代码演示了双向链表开头的插入操作。

//insert link at the first location
public void insertFirst(int key, int data){
   //create a link
   Link link = new Link(key,data);

   if(isEmpty()){
      //make it the last link
      last = link;
   }else {
      //update first prev link
      first.prev = link;
   }

   //point it to old first link
   link.next = first;
   //point first to new first link
   first = link;
}

删除操作

以下代码演示了双向链表开头的删除操作。

//delete link at the first location
public Link deleteFirst(){
   //save reference to first link
   Link tempLink = first;
   //if only one link
   if(first.next == null){
      last = null;
   }else {
      first.next.prev = null;
   }
   first = first.next;
   //return the deleted link
   return tempLink;
}

操作结束时插入

以下代码演示了双向链表中最后位置的插入操作。

//insert link at the last location
public void insertLast(int key, int data){
   //create a link
   Link link = new Link(key,data);

   if(isEmpty()){
      //make it the last link
      last = link;
   }else {
      //make link a new last link
      last.next = link;     
      //mark old last node as prev of new link
      link.prev = last;
   }

   //point last to new last node
   last = link;
}

演示

链接.java

package com.tutorialspoint.list;

public class Link {
   public int key;
   public int data;
   public Link next;
   public Link prev;

   public Link(int key, int data){
      this.key = key;
      this.data = data;
   }

   public void display(){
      System.out.print("{"+key+","+data+"}");
   }
}

双链表.java

package com.tutorialspoint.list;

public class DoublyLinkedList {
   
   //this link always point to first Link 
   private Link first;
   //this link always point to last Link 
   private Link last;

   // create an empty linked list 
   public DoublyLinkedList(){
      first = null;
      last = null;
   }

   //is list empty
   public boolean isEmpty(){
      return first == null;
   }

   //insert link at the first location
   public void insertFirst(int key, int data){
      //create a link
      Link link = new Link(key,data);

      if(isEmpty()){
         //make it the last link
         last = link;
      }else {
         //update first prev link
         first.prev = link;
      }

      //point it to old first link
      link.next = first;
      //point first to new first link
      first = link;
   }

   //insert link at the last location
   public void insertLast(int key, int data){
      //create a link
      Link link = new Link(key,data);

      if(isEmpty()){
         //make it the last link
         last = link;
      }else {
         //make link a new last link
         last.next = link;     
         //mark old last node as prev of new link
         link.prev = last;
      }

      //point last to new last node
      last = link;
   }

   //delete link at the first location
   public Link deleteFirst(){
      //save reference to first link
      Link tempLink = first;
      //if only one link
      if(first.next == null){
         last = null;
      }else {
         first.next.prev = null;
      }
      first = first.next;
      //return the deleted link
      return tempLink;
   }

   //delete link at the last location
   public Link deleteLast(){
      //save reference to last link
      Link tempLink = last;
      //if only one link
      if(first.next == null){
         first = null;
      }else {
         last.prev.next = null;
      }
      last = last.prev;
      //return the deleted link
      return tempLink;
   }

   //display the list in from first to last
   public void displayForward(){
      //start from the beginning
      Link current = first;
      //navigate till the end of the list
      System.out.print("[ ");
      while(current != null){
         //print data
         current.display();
         //move to next item
         current = current.next;
         System.out.print(" ");
      }      
      System.out.print(" ]");
   }

   //display the list from last to first
   public void displayBackward(){
      //start from the last
      Link current = last;
      //navigate till the start of the list
      System.out.print("[ ");
      while(current != null){
         //print data
         current.display();
         //move to next item
         current = current.prev;
         System.out.print(" ");
      }
      System.out.print(" ]");
   }

   //delete a link with given key
   public Link delete(int key){
      //start from the first link
      Link current = first;      
      //if list is empty
      if(first == null){
         return null;
      }

      //navigate through list
      while(current.key != key){
      //if it is last node
      if(current.next == null){
            return null;
         }else{           
            //move to next link
            current = current.next;             
         }
      }

      //found a match, update the link
      if(current == first) {
         //change first to point to next link
            first = current.next;
         }else {
            //bypass the current link
            current.prev.next = current.next;
         }    

         if(current == last){
            //change last to point to prev link
            last = current.prev;
         }else {
            current.next.prev = current.prev;
         }
         return current;
      }

   public boolean insertAfter(int key, int newKey, int data){
      //start from the first link
      Link current = first;      
      //if list is empty
      if(first == null){
         return false;
      }

      //navigate through list
      while(current.key != key){
         //if it is last node
         if(current.next == null){
            return false;
         }else{           
            //move to next link
            current = current.next;             
         }
      }

      Link newLink = new Link(newKey,data); 
      if(current==last) {
         newLink.next = null; 
         last = newLink; 
      }
      else {
         newLink.next = current.next;         
         current.next.prev = newLink;
      }
      newLink.prev = current; 
      current.next = newLink; 
      return true; 
   }
}

DoubleLinkedListDemo.java

package com.tutorialspoint.list;

public class DoublyLinkedListDemo {
    public static void main(String args[]){
        DoublyLinkedList list = new DoublyLinkedList();
        
        list.insertFirst(1, 10);
        list.insertFirst(2, 20);
        list.insertFirst(3, 30);
        
        list.insertLast(4, 1);
        list.insertLast(5, 40);
        list.insertLast(6, 56);
       
        System.out.print("\nList (First to Last): ");  
        list.displayForward();
        System.out.println("");
        System.out.print("\nList (Last to first): "); 
        list.displayBackward();
        
        System.out.print("\nList , after deleting first record: ");
        list.deleteFirst();        
        list.displayForward();
        
        System.out.print("\nList , after deleting last record: ");  
        list.deleteLast();
        list.displayForward();
        
        System.out.print("\nList , insert after key(4) : ");  
        list.insertAfter(4,7, 13);
        list.displayForward();
        
        System.out.print("\nList  , after delete key(4) : ");  
        list.delete(4);
        list.displayForward();
        
    }
}

如果我们编译并运行上面的程序，那么它将产生以下结果 -

List (First to Last): [ {3,30} {2,20} {1,10} {4,1} {5,40} {6,56}  ]

List (Last to first): [ {6,56} {5,40} {4,1} {1,10} {2,20} {3,30}  ]
List (First to Last) after deleting first record: [ {2,20} {1,10} {4,1} {5,40} {6,56}  ]
List  (First to Last) after deleting last record: [ {2,20} {1,10} {4,1} {5,40}  ]
List  (First to Last) insert after key(4) : [ {2,20} {1,10} {4,1} {7,13} {5,40}  ]
List  (First to Last) after delete key(4) : [ {2,20} {1,10} {7,13} {5,40}  ]

使用 Java 的 DSA - 循环链表

循环链表基础知识

循环链表是链表的一种变体，其中第一个元素指向最后一个元素，最后一个元素指向第一个元素。单链表和双向链表都可以做成循环链表

作为循环的单向链表

循环双向链表

根据上图所示，以下是需要考虑的要点。

在单链表和双链表两种情况下，Last Link'next 都指向列表的第一个链接。
在双向链表的情况下，第一个链接的 prev 指向列表的最后一个。

基本操作

以下是循环列表支持的重要操作。

insert - 在列表的开头插入一个元素。
删除- 从列表的开头插入一个元素。
显示- 显示列表。

长度操作

以下代码演示了基于单链表的循环链表中的插入操作。

//insert link at the first location
public void insertFirst(int key, int data){
   //create a link
   Link link = new Link(key,data);
   if (isEmpty()) {
      first  = link;
      first.next = first;
   }      
   else{
      //point it to old first node
      link.next = first;
      //point first to new first node
      first = link;
   }      
}

删除操作

下面的代码演示了基于单链表的循环链表中的删除操作。

//delete link at the first location
public Link deleteFirst(){
   //save reference to first link
   Link tempLink = first;
   //if only one link
   if(first.next == null){
      last = null;
   }else {
      first.next.prev = null;
   }
   first = first.next;
   //return the deleted link
   return tempLink;
}

显示列表操作

以下代码演示了循环链表中的显示列表操作。

public void display(){  
   //start from the beginning
   Link current = first;
   //navigate till the end of the list
   System.out.print("[ ");
   if(first != null){
      while(current.next != current){
         //print data
         current.display();
         //move to next item
         current = current.next;
         System.out.print(" ");
      }
   }
   System.out.print(" ]");
}

演示

链接.java

package com.tutorialspoint.list;
   
public class CircularLinkedList {
   //this link always point to first Link 
   private Link first;

   // create an empty linked list 
   public CircularLinkedList(){
      first = null;       
   }

   public boolean isEmpty(){
      return first == null;
   }

   public int length(){
      int length = 0;

      //if list is empty
      if(first == null){
         return 0;
      }

      Link current = first.next;

      while(current != first){
         length++;
         current = current.next;   
      }
      return length;
   }

   //insert link at the first location
   public void insertFirst(int key, int data){
   //create a link
   Link link = new Link(key,data);
      if (isEmpty()) {
         first  = link;
         first.next = first;
      }      
      else{
         //point it to old first node
         link.next = first;
         //point first to new first node
         first = link;
      }      
   }

   //delete first item
   public Link deleteFirst(){
      //save reference to first link
      Link tempLink = first;
      if(first.next == first){  
         first = null;
         return tempLink;
      }     

      //mark next to first link as first 
      first = first.next;
      //return the deleted link
      return tempLink;
   }

   public void display(){

      //start from the beginning
      Link current = first;
      //navigate till the end of the list
      System.out.print("[ ");
      if(first != null){
         while(current.next != current){
            //print data
            current.display();
            //move to next item
            current = current.next;
            System.out.print(" ");
         }
      }
      System.out.print(" ]");
   }   
}

DoubleLinkedListDemo.java

package com.tutorialspoint.list;

public class CircularLinkedListDemo {
   public static void main(String args[]){
      CircularLinkedList list = new CircularLinkedList();

      list.insertFirst(1, 10);
      list.insertFirst(2, 20);
      list.insertFirst(3, 30);
      list.insertFirst(4, 1);
      list.insertFirst(5, 40);
      list.insertFirst(6, 56);

      System.out.print("\nOriginal List: ");  
      list.display();
      System.out.println("");  
      while(!list.isEmpty()){            
         Link temp = list.deleteFirst();
         System.out.print("Deleted value:");  
         temp.display();
         System.out.println("");
      }         
      System.out.print("List after deleting all items: ");          
      list.display();
      System.out.println("");
   }
}

如果我们编译并运行上面的程序，那么它将产生以下结果 -

Original List: [ {6,56} {5,40} {4,1} {3,30} {2,20}  ]
Deleted value:{6,56}
Deleted value:{5,40}
Deleted value:{4,1}
Deleted value:{3,30}
Deleted value:{2,20}
Deleted value:{1,10}
List after deleting all items: [  ]

使用Java的DSA - 堆栈内存溢出

概述

堆栈是一种只允许在一端对数据进行操作的数据结构。它只允许访问最后插入的数据。堆栈也称为 LIFO（后进先出）数据结构，Push 和 Pop 操作以这样的方式相关：只有最后压入（添加到堆栈）的项目才能弹出（从堆栈中删除）。

堆栈表示

在本文中，我们将使用数组来实现 Stack。

基本操作

以下是堆栈的两个主要操作。

Push - 将一个元素压入栈顶。
Pop - 从堆栈顶部弹出一个元素。

以下是堆栈支持的更多操作。

Peek - 获取堆栈顶部的元素。
isFull - 检查堆栈是否已满。
isEmpty - 检查堆栈是否为空。

推送操作

每当一个元素被推入堆栈时，堆栈就会将该元素存储在存储的顶部，并递增顶部索引以供以后使用。如果存储已满，通常会显示错误消息。

// push item on the top of the stack 
public void push(int data) {

   if(!isFull()){
      // increment top by 1 and insert data 
      intArray[++top] = data;
   }else{
      System.out.println("Cannot add data. Stack is full.");
   }      
}

流行操作

每当要从堆栈中弹出一个元素时，堆栈都会从存储顶部检索该元素，并减少顶部索引以供以后使用。

// pop item from the top of the stack 
public int pop() {
   // retrieve data and decrement the top by 1 
   return intArray[top--];        
}

堆栈实现

堆栈.java

package com.tutorialspoint.datastructure;

public class Stack {
   private int size;           // size of the stack
   private int[] intArray;     // stack storage
   private int top;            // top of the stack

   // Constructor 
   public Stack(int size){
      this.size = size;           
      intArray = new int[size];   //initialize array
      top = -1;                   //stack is initially empty
   }

   // Operation : Push
   // push item on the top of the stack 
   public void push(int data) {

      if(!isFull()){
         // increment top by 1 and insert data 
         intArray[++top] = data;
      }else{
         System.out.println("Cannot add data. Stack is full.");
      }      
   }

   // Operation : Pop
   // pop item from the top of the stack 
   public int pop() {
      //retrieve data and decrement the top by 1
      return intArray[top--];        
   }

   // Operation : Peek
   // view the data at top of the stack    
   public int peek() {       
      //retrieve data from the top
      return intArray[top];
   }

   // Operation : isFull
   // return true if stack is full 
   public boolean isFull(){
      return (top == size-1);
   }
   
   // Operation : isEmpty
   // return true if stack is empty 
   public boolean isEmpty(){
      return (top == -1);
   }
}

演示程序

StackDemo.java

package com.tutorialspoint.datastructure;

public class StackDemo {
   public static void main (String[] args){

      // make a new stack
      Stack stack = new Stack(10);

      // push items on to the stack
      stack.push(3);
      stack.push(5);
      stack.push(9);
      stack.push(1);
      stack.push(12);
      stack.push(15);

      System.out.println("Element at top of the stack: " + stack.peek());
      System.out.println("Elements: ");
	  
      // print stack data 
      while(!stack.isEmpty()){
         int data = stack.pop();
         System.out.println(data);
      }
	         
      System.out.println("Stack full: " + stack.isFull());
      System.out.println("Stack empty: " + stack.isEmpty());
   }
}

如果我们编译并运行上面的程序，那么它将产生以下结果 -

Element at top of the stack: 15
Elements: 
15
12
1
9
5
3
Stack full: false
Stack empty: true

使用 Java 的 DSA - 解析表达式

像 2*(3*4) 这样的普通算术表达式对于人类来说更容易解析，但对于算法来说解析这样的表达式是相当困难的。为了缓解这一困难，可以通过使用两步方法的算法来解析算术表达式。

将提供的算术表达式转换为后缀表示法。
评估后缀表示法。

中缀表示法

正常算术表达式遵循中缀表示法，其中运算符位于操作数之间。例如 A+B，这里 A 是第一个操作数，B 是第二个操作数，+ 是作用于两个操作数的运算符。

后缀表示法

后缀表示法与普通算术表达式或中缀表示法的不同之处在于运算符位于操作数之后。例如，考虑以下示例

先生编号	中缀表示法	后缀表示法
1	A+B	AB+
2	(A+B)*C	AB+C*
3	A*(B+C)	ABC+*
4	A/B+C/D	AB/CD/+
5	(A+B)*(C+D)	AB+CD+*
6	((A+B)*C)-D	AB+C*D-

中缀到后缀转换

在研究如何将中缀转换为后缀表示法之前，我们需要考虑以下中缀表达式求值的基础知识。

中缀表达式的计算从左到右开始。
请记住优先级，例如 * 的优先级高于 +。例如
- 2+3*4 = 2+12。
- 2+3*4 = 14。
使用括号覆盖优先级，例如
- (2+3)*4 = 5*4。
- (2+3)*4=20。

现在让我们手动将一个简单的中缀表达式 A+B*C 转换为后缀表达式。

步	字符读取	到目前为止已解析的中缀表达	后缀表达式发展至今	评论
1	A	A	A
2	+	A+	A
3	乙	A+B	AB
4	*	A+B*	AB	+ 无法复制，因为 * 具有更高的优先级。
5	C	A+B*C	ABC
6		A+B*C	ABC*	复制 * 作为两个操作数 B 和 C
7		A+B*C	ABC*+	复制 + 作为两个操作数 BC 和 A

现在让我们使用堆栈将上面的中缀表达式 A+B*C 转换为后缀表达式。

步	字符读取	到目前为止已解析的中缀表达	后缀表达式发展至今	堆栈内容	评论
1	A	A	A
2	+	A+	A	+	将 + 运算符压入堆栈。
3	乙	A+B	AB	+
4	*	A+B*	AB	+*	运算符 * 的优先级高于 +。将 * 运算符推入堆栈。否则会弹出+。
5	C	A+B*C	ABC	+*
6		A+B*C	ABC*	+	没有更多的操作数，弹出 * 运算符。
7		A+B*C	ABC*+		弹出 + 运算符。

现在让我们看另一个例子，通过使用堆栈将中缀表达式 A*(B+C) 转换为后缀表达式。

步	字符读取	到目前为止已解析的中缀表达	后缀表达式发展至今	堆栈内容	评论
1	A	A	A
2	*	A*	A	*	将 * 运算符推入堆栈。
3	（	A*（	A	*(	将 ( 推入堆栈。
4	乙	A*(B	AB	*(
5	+	A*(B+	AB	*(+	将 + 压入堆栈。
6	C	A*(B+C	ABC	*(+
7	）	A*(B+C)	ABC+	*(	弹出 + 运算符。
8		A*(B+C)	ABC+	*	弹出 ( 运算符。
9		A*(B+C)	ABC+*		弹出其余的运算符。

演示程序

现在我们将演示如何使用堆栈将中缀表达式转换为后缀表达式，然后计算后缀表达式。

堆栈.java

package com.tutorialspoint.expression;

public class Stack {

   private int size;           
   private int[] intArray;     
   private int top;            

   //Constructor
   public Stack(int size){
      this.size = size;           
      intArray = new int[size];   
      top = -1;                   
   }

   //push item on the top of the stack
   public void push(int data) {
      if(!isFull()){
         //increment top by 1 and insert data
         intArray[++top] = data;
      }else{
         System.out.println("Cannot add data. Stack is full.");
      }      
   }

   //pop item from the top of the stack
   public int pop() {
      //retrieve data and decrement the top by 1
      return intArray[top--];        
   }

   //view the data at top of the stack
   public int peek() {       
      //retrieve data from the top
      return intArray[top];
   }

   //return true if stack is full
   public boolean isFull(){
      return (top == size-1);
   }

   //return true if stack is empty
   public boolean isEmpty(){
      return (top == -1);
   }
}

InfixToPostFix.java

package com.tutorialspoint.expression;

public class InfixToPostfix {
   private Stack stack;
   private String input = "";
   private String output = "";

   public InfixToPostfix(String input){
      this.input = input;
      stack = new Stack(input.length());
   }

   public String translate(){
      for(int i=0;i<input.length();i++){
         char ch = input.charAt(i);
            switch(ch){
               case '+':
               case '-':
                  gotOperator(ch, 1);
                  break;
               case '*':
               case '/':
                  gotOperator(ch, 2);
                  break;
               case '(':
                  stack.push(ch);
                  break;
               case ')':
                  gotParenthesis(ch);
                  break;
               default:
                  output = output+ch;            
                  break;
          }
      }

      while(!stack.isEmpty()){
         output = output + (char)stack.pop();
      }       

      return output;
   }   

      //got operator from input
      public void gotOperator(char operator, int precedence){
      while(!stack.isEmpty()){
         char prevOperator = (char)stack.pop();
         if(prevOperator == '('){
            stack.push(prevOperator);
            break;
         }else{
            int precedence1;
            if(prevOperator == '+' || prevOperator == '-'){
               precedence1 = 1;
            }else{
               precedence1 = 2;
            }

            if(precedence1 < precedence){
               stack.push(Character.getNumericValue(prevOperator));
               break;                        
            }else{
               output = output + prevOperator;
            }                
         }   
      }
      stack.push(operator);
   }

   //got operator from input
   public void gotParenthesis(char parenthesis){
      while(!stack.isEmpty()){
         char ch = (char)stack.pop();
         if(ch == '('){                
            break;
         }else{
            output = output + ch;               
         }   
      }        
   } 
}

PostFixParser.java

package com.tutorialspoint.expression;

public class PostFixParser {
private Stack stack;
private String input;

public PostFixParser(String postfixExpression){
   input = postfixExpression;
   stack = new Stack(input.length());
}

   public int evaluate(){
      char ch;
      int firstOperand;
      int secondOperand;
      int tempResult;

      for(int i=0;i<input.length();i++){
         ch = input.charAt(i);

         if(ch >= '0' && ch <= '9'){
            stack.push(Character.getNumericValue(ch));
         }else{
            firstOperand = stack.pop();
            secondOperand = stack.pop();
            switch(ch){
               case '+':
                  tempResult = firstOperand + secondOperand;
                  break;
               case '-':
                  tempResult = firstOperand - secondOperand;
                  break;
               case '*':
                  tempResult = firstOperand * secondOperand;
                  break;
               case '/':
                  tempResult = firstOperand / secondOperand;
                  break;   
               default:
                  tempResult = 0;
            }
            stack.push(tempResult);
         }
      }
      return stack.pop();
   }       
}

PostFixDemo.java

package com.tutorialspoint.expression;

public class PostFixDemo {
   public static void main(String args[]){
      String input = "1*(2+3)";
      InfixToPostfix translator = new InfixToPostfix(input);
      String output = translator.translate();
      System.out.println("Infix expression is: " + input);
      System.out.println("Postfix expression is: " + output);

      PostFixParser parser = new PostFixParser(output);
      System.out.println("Result is: " + parser.evaluate());
   }
}

如果我们编译并运行上面的程序，那么它将产生以下结果 -

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Result is: 5

使用 Java 的 DSA - 队列

概述

队列是一种类似于堆栈的数据结构，主要区别在于插入的第一个项目是要删除的第一个项目（FIFO - 先进先出），其中堆栈基于 LIFO（后进先出）原理。

队列表示

基本操作

insert / enqueue - 将一个项目添加到队列的末尾。
删除/出队- 从队列前面删除一个项目。

在本文中，我们将使用数组来实现队列。下面还有一些队列支持的操作。

Peek - 获取队列前面的元素。
isFull - 检查队列是否已满。

使用 Java 的 DSA - 快速指南

使用 Java 的 DSA - 概述

什么是数据结构？

数据结构的特征

对数据结构的需求

执行时间案例

使用 Java 的 DSA - 环境设置

本地环境设置

设置 Windows 2000/XP 的路径

设置Windows 95/98/ME的路径

设置 Linux、UNIX、Solaris、FreeBSD 的路径：

流行的 Java 编辑器

下一步是什么 ？

使用 Java 的 DSA - 算法

算法概念

算法分析

渐近分析

渐近符号

大哦符号，Ο

欧米茄表示法，Ω

Theta 表示法，θ

使用 Java 的 DSA - 数据结构

数据定义

数据对象

数据类型

内置数据类型

派生数据类型

使用 Java 的 DSA - 数组

数组基础知识

数组表示

基本操作

演示

使用 Java 的 DSA - 链表

链表基础知识

链表表示

链表的类型

基本操作

插入操作

删除操作

导航操作

高级操作

排序操作

反向操作

连接操作

演示

使用 Java 的 DSA - 双向链表

双向链表基础知识

双向链表表示

基本操作

插入操作

删除操作

操作结束时插入

演示

使用 Java 的 DSA - 循环链表

循环链表基础知识

作为循环的单向链表

循环双向链表

基本操作

长度操作

删除操作

显示列表操作

演示

使用Java的DSA - 堆栈内存溢出

概述

堆栈表示

基本操作

推送操作

流行操作

堆栈实现

演示程序

使用 Java 的 DSA - 解析表达式

中缀表示法

后缀表示法

中缀到后缀转换

演示程序

使用 Java 的 DSA - 队列

概述

队列表示

基本操作

下一步是什么？