使用 Java 的 DSA - 链接列表
链接列表基础知识
链接列表是包含项目的链接序列。每个链接都包含与另一个链接的连接。链接列表是继数组之后第二常用的数据结构。以下是理解链接列表概念的重要术语。
链接 − 链接列表的每个链接都可以存储称为元素的数据。
下一个 − 链接列表的每个链接都包含指向下一个链接的链接，称为下一个。
LinkedList − LinkedList 包含指向第一个 Link 的连接链接，称为 First。
Linked List 表示
如上图所示，以下是需要考虑的重要点。
LinkedList 包含一个名为 first 的链接元素。
每个 Link 都带有一个数据字段和一个称为 next 的链接字段。
每个 Link 都使用其下一个链接与其下一个链接链接。
Last Link 带有一个 Link 作为 null 来标记列表的结尾。
Linked List 的类型
以下是各种类型的 Link列表。
简单链接列表 − 项目导航仅向前。
双向链接列表 − 项目可以向前和向后导航。
循环链接列表 − 最后一项包含第一个元素的链接作为下一个，并且第一个元素具有到最后一个元素的链接作为上一个。
基本操作
以下是列表支持的基本操作。
插入 − 在列表开头添加一个元素。
删除 −删除列表开头的一个元素。
显示 − 显示完整列表。
搜索 − 使用给定的键搜索元素。
删除 − 使用给定的键删除元素。
插入操作
插入分为三个步骤:
使用提供的数据创建新链接。
将新链接指向旧的第一个链接。
将第一个链接指向此新链接。
//在第一个位置插入链接
public void insertFirst(int key, int data){
//创建链接
Link link = new Link(key,data);
//将其指向旧的第一个节点
link.next = first;
//将 first 指向新的第一个节点
first = link;
}
删除操作
删除分为两个步骤:
获取 First Link 指向的链接作为临时链接。
将 First Link 指向临时链接的下一个链接。
//删除第一项
public Link deleteFirst(){
//保存对第一个链接的引用
Link tempLink = first;
//将第一个链接旁边的标记为第一个
first = first.next;
//返回删除的链接
return tempLink;
}
导航操作
导航是一个递归步骤过程，是搜索、删除等许多操作的基础:
获取第一个链接指向的链接作为当前链接。
检查当前链接是否不为空并显示它。
将当前链接指向当前链接的下一个链接并移动到上一步。
注意
//显示列表
public void display(){
//从头开始
Link current = first;
//导航到列表末尾
System.out.print("[ ");
while(current != null){
//打印数据
current.display();
//移动到下一个项目
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;
reverselist.insertFirst(first.key, first.data);
Link currentLink = first;
// 直到列表中没有更多数据，
// 在第一个之前插入当前链接并向前移动。
while(currentLink.next != null){
nextLink = currentLink.next;
// 在新列表的开头插入。
reverselist.insertFirst(nextLink.key, nextLink.data);
//前进到下一个节点
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;
}
演示
Link.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+"}");
}
}
LinkedList.java
package com.tutorialspoint.list;
public class LinkedList {
//此链接始终指向链接列表中的第一个链接
//private Link first;
//创建一个空链接列表
public LinkedList(){
first = null;
}
//在第一个位置插入链接
public void insertFirst(int key, int data){
//创建链接
Link link = new Link(key,data);
//将其指向旧的第一个节点
link.next = first;
//将 first 指向新的第一个节点
first = link;
}
//delete first item
public Link deleteFirst(){
//保存对第一个链接的引用
Link tempLink = first;
//将第一个链接旁边的标记为第一个
first = first.next;
//返回删除的链接
return tempLink;
}
//display the list
public void display(){
//从头开始
Link current = first;
//导航到列表末尾
System.out.print("[ ");
while(current != null){
//打印数据
current.display();
//移动到下一个项目
current = current.next;
System.out.print(" ");
}
System.out.print(" ]");
}
//找到具有给定键的链接
public Link find(int key){
//从第一个链接开始
Link current = first;
//如果列表为空
if(first == null){
return null;
}
//浏览列表
while(current.key != key){
//如果它是最后一个节点
if(current.next == null){
return null;
}else{
//转到下一个链接
current = current.next;
}
}
//如果找到数据，返回当前链接
return current;
}
//删除指定键的链接
public Link delete(int key){
//从第一个链接开始
Link current = first;
Link previous = null;
//如果列表为空
if(first == null){
return null;
}
//浏览列表
while(current.key != key){
//如果它是最后一个节点
if(current.next == null){
return null;
}else{
//存储对当前链接的引用
previous = current;
//移动到下一个链接
current = current.next;
}
}
//找到匹配项，更新链接
if(current == first) {
//将 first 改为指向 next 链接
first = first.next;
}else {
//绕过当前链接
previous.next = current.next;
}
return current;
}
//列表是否为空
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;
// 直到列表中没有更多数据，
// 在第一个链接之前插入当前链接并继续前进。
while(currentLink.next != null){
nextLink = currentLink.next;
// 插入到新列表的开头。
reversedlist.insertFirst(nextLink.key, nextLink.data);
//前进到下一个节点
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("原始列表: ");
list.display();
System.out.println("");
while(!list.isEmpty()){
Link temp = list.deleteFirst();
System.out.print("删除的值:");
temp.display();
System.out.println("");
}
System.out.print("删除所有项目后的列表: ");
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("");
}
}
如果我们编译并运行上述程序，则会产生以下结果:
原始列表: [ {6,56} {5,40} {4,1} {3,30} {2,20} {1,10} ]
删除的值:{6,56}
删除的值:{5,40}
删除的值:{4,1}
删除的值:{3,30}
删除的值:{2,20}
删除的值:{1,10}
删除所有项目后的列表: [ ]
恢复的列表:[ {6,56} {5,40} {4,1} {3,30} {2,20} {1,10} ]
找到元素:{4,1}
删除项目后的列表:[ {6,56} {5,40} {3,30} {2,20} {1,10} ]
未找到元素。{4,1}
对数据进行排序后的列表:[ {1,10} {2,20} {3,30} {5,40} {6,56} ]
列表的反转:[ {6,56} {5,40} {3,30} {2,20} {1,10} ]
连接后的列表:[ {1,10} {2,20} {3,30} {5,40} {6,56} {7,20} {8,40} {9,50} ]
