Thường thì trong C/C++ các bạn thường dùng các danh sách liên kết đôi, danh sách liên kết đơn hơn là trong các ngôn ngữ khác. Nhưng nay mình muốn chia sẻ tới các bạn ví dụ code danh sách liên kết đôi trong java. Về cấu trúc hay cách hoạt động thì nó cũng giống như trong C/C++ mà thôi. Chỉ khác ngôn ngữ code ^ _ ^ . Mình dùng Netbeans IDE 8.2 code nha.
Danh sách liên kết đôi trong Java
- Thêm danh sách liên kết
- In danh sách liên kết
- Tìm kiếm k trong danh sách liên kết
- Thêm danh sách liên kết
- Thêm Node vào đầu danh sách liên kết
- Thêm Node vào trước khóa k trong danh sách liên kết
- Thêm Node vào sau khóa k trong danh sách liên kết
- Xoá phần tử có khoá k
- Xoá phần tử đầu danh sách
- Xoá phần tử trước phần tử có khoá k
- Xoá phần tử sau phần tử có khoá k
- Xoá phần tử cuối danh sách
Triển khai code
Bước 1: Tạo Project các bạn chọn File ⇨ New Project ⇨ Java ⇨ Java Application để tạo 1 project với tên là DSLK_DOI
Khi đó IDE sẽ tự tạo cho chúng ta 1 project với 1 class là DSLK_DOI.java bạn code các chức năng hiển thị trong file như sau:
import java.util.Scanner;
/**
*
@author Tuan-PC
*/
public class DSLK_DOI {
/**
@param args the command line arguments
*/
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int lc;
Node node;
int temp, k;
lien_ket_doi lk = new lien_ket_doi();
do {
lc = luachon(scanner);
switch (lc) {
case 0:
break;
case 1:
System.out.print("Nhập vào số lượng Node : ");
int slData = scanner.nextInt();
for (int i=0; i < slData; i++) {
System.out.print("- Nhập vào Data : ");
temp = scanner.nextInt();
lk.Add(temp);
}
break;
case 2:
lk.Print();
break;
case 3:
System.out.print("Nhập Data khoá k cần tìm : ");
temp = scanner.nextInt();
node = lk.Find(temp);
if (node == null) {
System.out.println("Không tìm thấy Node có chứa khoá " + temp);
}else {
System.out.println("Tìm thấy node có chứa khoá " + node.Data);
}
break;
case 4:
System.out.print("Nhập Data khoá k cần tìm : ");
temp = scanner.nextInt();
node = lk.Find(temp);
if (node == null) {
System.out.println("Không tìm thấy Node có chứa khoá " + temp);
}else {
System.out.print("Giá trị cần thay thế khoá " + node.Data + " : ");
temp = scanner.nextInt();
node.Data = temp;
}
break;
case 5:
System.out.println("Thêm vào đầu danh sách.");
System.out.print("Nhập vào Data : ");
temp = scanner.nextInt();
lk.AddFirst(temp);
break;
case 6:
System.out.println("Thêm node vào trước khoá k");
System.out.print("Nhập vào khoá k = ");
k = scanner.nextInt();
System.out.print("Nhập vào Data : ");
temp = scanner.nextInt();
lk.AddFirstk(k, temp);
break;
case 7:
System.out.println("Thêm node vào sau khoá k");
System.out.print("Nhập vào khoá k = ");
k = scanner.nextInt();
System.out.print("Nhập vào Data : ");
temp = scanner.nextInt();
lk.AddAfterk(k, temp);
break;
case 8:
System.out.println("Xoá phần tử có khoá k");
System.out.print("Nhập vào khoá k : ");
k = scanner.nextInt();
node = new Node(k);
lk.Deletek(node);
break;
case 9:
System.out.println("Xoá phần tử đầu.");
lk.DeleteFirst();
break;
case 10:
System.out.println("Xoá phần tử trước phần tử có khoá k.");
System.out.print("Nhập vào khoá k : ");
k = scanner.nextInt();
node = new Node(k);
lk.DeleteFirstk(node);
break;
case 11:
System.out.println("Xoá phần tử sau phần tử có khoá k.");
System.out.print("Nhập vào khoá k : ");
k = scanner.nextInt();
node = new Node(k);
lk.DeleteAfterk(node);
break;
case 12:
System.out.println("Xoá phần tử cuối danh sách.");
lk.DeleteAfter();
break;
}
}while(lc !=0);
}
public static int luachon(Scanner scanner) {
System.out.println("--- Danh sách chức năng --- \n");
System.out.println("1 : Thêm danh sách liên kết \n");
System.out.println("2 : In danh sách liên kết \n");
System.out.println("3 : Tìm kiếm k trong danh sách liên kết \n");
System.out.println("4 : Thêm danh sách liên kết \n");
System.out.println("5 : Thêm Node vào đầu danh sách liên kết \n");
System.out.println("6 : Thêm Node vào trước khóa k trong danh sách liên kết \n");
System.out.println("7 : Thêm Node vào sau khóa k trong danh sách liên kết \n");
System.out.println("8 : Xoá phần tử có khoá k \n");
System.out.println("9 : Xoá phần tử đầu danh sách \n");
System.out.println("10: Xoá phần tử trước phần tử có khoá k \n");
System.out.println("11: Xoá phần tử sau phần tử có khoá k \n");
System.out.println("12 : Xoá phần tử cuối danh sách \n");
System.out.print("Mời nhập lựa chọn : ");
int lc = scanner.nextInt();
return lc;
}
}Tiếp theo là file chứa các chức năng để hàm main có thể gọi tới và thực hiện.
public class lien_ket_doi {
Node head;
Node tail;
lien_ket_doi(){
head = tail = null;
}
lien_ket_doi(Node node){
Add(node);
}
public void Add(Node node) {
if (head == null) {
head = tail = node;
}else {
tail.next = node;
node.prev = tail;
tail = node;
}
}
public Node Find(int Data) {
Node now = head;
while (now != null) {
if (now.Data == Data) return now;
now = now.next;
};
return null;
}
public Node Find(Node node) {
return this.Find(node.Data);
}
public void AddFirst(Node node) {
node.next = head;
head.prev = node;
head = node;
}
public void AddFirst(int Data) {
Node node = new Node(Data);
this.AddFirst(node);
}
public void AddFirstk(int k, int Data) {
Node node = new Node(Data);
this.AddFirstk(k, node);
}
public void AddFirstk(int k, Node node) {
if (head == null) {
System.out.println("Danh sách rỗng.");
return;
};
if (head.Data == k) {
this.AddFirst(node);
return;
}
Node nodek = this.Find(k);
if (nodek == null) {
System.out.println("Không tìm thấy khoá k");
return;
}
nodek.prev.next = node;
node.prev = nodek.prev;
node.next = nodek;
nodek.prev = node;
}
public void AddAfterk(int k, int Data) {
Node node = new Node(Data);
this.AddAfterk(k, node);
}
public void AddAfterk(int k, Node node) {
Node nodek = this.Find(k);
if (nodek == null) {
System.out.println("Không tìm thấy khoá k");
return;
}
if (nodek.next == null) {
this.Add(node);
return;
}
node.next = nodek.next;
nodek.next.prev = node;
nodek.next = node;
node.prev = nodek;
if (node.next != null) tail = node;
}
public void Deletek(int k) {
Node node = new Node(k);
this.Deletek(node);
}
public void Deletek_New(Node k) {
Node node = this.Find(k);
if (node == null) return;
node = node.next;
}
public void Deletek(Node k) {
if (head == null) {
System.out.println("Danh sách rỗng.");
return;
};
if (head.Data == k.Data) {
this.DeleteFirst();
return;
}
Node nodek = this.Find(k);
if (nodek == null) {
System.out.println("Không tìm thấy khoá k");
return;
}
if (nodek.next == null) {
this.DeleteAfter();
return;
}
nodek.prev.next = nodek.next;
nodek.next.prev = nodek.prev;
}
public void DeleteFirst() {
if (head == null) return;
head = head.next;
if (head == null) tail = null;
}
public void DeleteFirstk(int k) {
Node node = new Node(k);
this.DeleteFirstk(node);
}
public void DeleteFirstk(Node node) {
if (head == null) return;
if (head.Data == node.Data) return;
if (head.next.Data == node.Data) {
this.DeleteFirst();
return;
}
Node nodek = this.Find(node);
nodek.prev.prev.next = nodek;
nodek.prev = nodek.prev.prev;
}
public void DeleteAfter() {
if (head == null) return;
if (head.next == null) {
this.DeleteFirst();
return;
}
tail.prev.next = null;
tail = tail.prev;
}
public void Delete() {
head = tail = null;
}
public void DeleteAfterk(Node node) {
Node k = this.Find(node);
if (k == null) {
System.out.println("Không tìm thấy khoá k");
return;
}
if (k.next == null) {
System.out.println("k không có phần tử phía sau.");
return;
}
if (k.next.next == null) {
this.DeleteAfter();
return;
}
k.next = k.next.next;
k.next.prev = k;
}
public void Add(int Data) {
Node node = new Node(Data);
this.Add(node);
}
public void Print() {
if (head == null) {
System.out.println("Danh sách liên kết rỗng, không thể in");
return;
}
System.out.println("Danh sách liên kết : ");
Node now = head;
while (now != null) {
now.Print();
now = now.next;
}
}
}
class Node{
int Data = 0;
Node next = null;
Node prev = null;
Node(){
}
Node(int Data){
this.Data = Data;
}
public void Print() {
System.out.println("\t- Data : " + this.Data);
}
}
