Dsa Using Java 简明教程
DSA using Java - Linked List
Linked List Basics
链表是由包含项的链接序列。每个链接都包含到另一个链接的连接。链表是在数组之后使用第二多的数据结构。以下是理解链表概念的重要术语。
-
Link − 链表的每个链接可以存储一个称为元素的数据。
-
Next − 链表的每个链接都包含到下一个链接的链接,称为 Next。
-
LinkedList − 一个 LinkedList 包含连接到称为 First 的第一个 Link 的连接链接。
Linked List Representation
根据以上所示的说明,以下是要考虑的重要要点。
-
双向链表包含第一个链接元素。
-
每个链接都包含一个数据字段(多个字段)和一个称为 Next 的链接字段。
-
每个链接使用其 Next 链接与其下一个链接链接。
-
最后一个链接包含一个空链接来标记链表的结尾。
Types of Linked List
以下是双向链表的各种类型。
-
Simple Linked List - 项目导航仅向前。
-
Doubly Linked List - 项目可以向前和向后导航。
-
Circular Linked List - 最后一个项目包含第一个元素的链接,而第一个元素包含指向最后一个元素的链接。
Basic Operations
以下是列表支持的基本操作。
-
Insertion − 在链表的开头添加元素。
-
Deletion − 删除链表开头的元素。
-
Display - 显示完整的列表。
-
Search - 使用给定的键搜索元素。
-
Delete - 使用给定的键删除元素。
Insertion Operation
插入是一个三步过程:
//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;
}
Deletion Operation
删除是一个两步过程:
//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;
}
Navigation Operation
导航是一个递归步骤过程,是许多操作(如搜索、删除等)的基础:
Note
//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(" ]");
}
Sort Operation
我们使用冒泡排序对列表进行排序。
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;
}
}
}
Reverse Operation
以下代码演示如何逆转一个单链表。
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;
}
Concatenate Operation
以下代码演示如何逆转一个单链表。
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;
}
Demo
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+"}");
}
}
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;
}
}
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} ]