[Java] Danh sách liên kết

Nội dung phần này tập trung cài đặt hai loại danh sách liên kết cơ bản:
•  Danh sách liên kết đơn
•  Danh sách liên kết kép
1. Định nghĩa một nút
Để đơn giản, ta chỉ định nghĩa một nút có giá trị kiểu int:

//Chương trình 1a
public class Node{
 private int value;
 /* Các phương thức khởi dựng */
 public Node(){
  value = 0;
 }
 public Node(int value){
  this.value = value;
 }
 /* Phương thức truy nhập thuộc tính value */
 public int getValue(){
  return value;
 }
 public void setValue(int value){
  this.value = value;
 }
}

2. Danh sách liên kết đơn
a. Định nghĩa một nút của danh sách liên kết đơn
Một nút của danh sách liên kết đơn bao gồm:
•  Giá trị của nút, có dạng là một đối tượng kiểu Node đã được định nghĩa trong chương trình 1a
•  Nút tiếp theo của nút đó.
Một nút của danh sách liên kết đơn được cài đặt trong chương trình 1b.

//Chương trình 1b
public class SimpleNode{
 private Node value;   // Giá trịcủa node là một đối tượng kiểu Node
 private SimpleNode next; // Node tiếp theo của danh sách liên kết 
 /* Các phương thức khởi dựng */
 public SimpleNode(){
  value = new Node();
  next = null;
 }
 public SimpleNode(Node value){
  this.value = value;
  next = null;
 }
 /* Phương thức truy nhập thuộc tính value */
 public Node getValue(){
  return value;
 }
 public void setValue(Node value){
  this.value = value;
 }
 /* Phương thức truy nhập thuộc tính next */
 public SimpleNode getNext(){
  return next;
 }
 public void setNext(SimpleNode next){
  this.next = next;
 }
}

b. Định nghĩa đỉnh tiêu đề của danh sách liên kết đơn
Đỉnh tiêu đề của danh sách liên kết đơn là một đối tượng khác với một nút thông thường của danh sách. Đối tượng này lưu các thông tin:
•  Chỉ đến nút thực sự đầu tiên của danh sách
•  Chỉ đến nút cuối cùng của danh sách
•  Lưu giữ số lượng nút thực sự trong danh sách.
Chương trình 1c cài đặt lớp đỉnh tiêu đề của danh sách.

//Chương trình 1c
public class HeaderSimpleNode{
 private int nodeNumber;
 private SimpleNode header;
 private SimpleNode tailer;
 /* Phương thức khởi dựng */
 public HeaderSimpleNode(){
  nodeNumber = 0;
  header = null;
  tailer = null;
 }
 /* Phương thức truy nhập thuộc tính nodeNumber */
 public int getNodeNumber(){
  return nodeNumber;
 }
 public void setNodeNumber(int nodeNumber){
  this.nodeNumber = nodeNumber;
 }
 /* Phương thức truy nhập thuộc tính header */
 public SimpleNode getHeader(){
  return header;
 }
 public void setHeader(SimpleNode header){
  this.header = header;
 }
 /* Phương thức truy nhập thuộc tính tailer */
 public SimpleNode getTailer(){
  return tailer;
 }
 public void setTailer(SimpleNode tailer){
  this.tailer = tailer;
 }
}

c. Cài đặt danh sách liên kết đơn
Danh sách liên kết đơn có thuộc tính cục bộ là một đối tượng kiểu HeaderSimpleNode. Và có các thao tác chính:
 • Thêm một phần tử vào một vịtrí bất kì: nếu vịtrí nhỏ hơn 0, thêm vào đầu danh sách. Nếu vị trí lớn hơn độ dài danh sách, thêm vào cuối. Trường hợp còn lại, chèn vào danh sách một cách bình thường. • Loại bỏ một phần tử ở vị trí bất kì: Chỉ loại bỏ khi vị trí chỉ ra nằm trong phạm vi độ dài danh sách. Phương thức này trả về nút bị loại bỏ, có kiểu SimpleNode.
 • Duyệt toàn bộ danh sách: Trả về giá trị của tất cả các phần tử có trong danh sách. Giá trịtrả về là một mảng các phần tử giá trị có kiểu Node.
Chương trình 1d cài đặt lớp danh sách liên kết đơn.

//Chương trình 1d
public class SimpleList{
 private HeaderSimpleNode myList;
 /* Các phương thức khởi dựng */
 public SimpleList(){
  myList = new HeaderSimpleNode();
 }
 /* Phương thức chèn thêm một node vào vịtrí @position */
 public void insert(Node value, int position){
  // Tạo một node mới 
  SimpleNode newNode = new SimpleNode(value);
  if (position <= 0){ // Chèn vào đầu 
   newNode.setNext(myList.getHeader());
   myList.setHeader(newNode);
   if (myList.getNodeNumber() == 0) // Danh sách ban đầu rỗng 
    myList.setTailer(newNode);
  }
  else if (position >= myList.getNodeNumber()){ // Chèn vào cuối 
   if (myList.getNodeNumber() == 0){ // Danh sách ban đầu rỗng 
    myList.setHeader(newNode);
    myList.setTailer(newNode);
   }
   else{ // Danh sách không rỗng 
    myList.getTailer().setNext(newNode);
    myList.setTailer(newNode);
   }
  }
  else{ // Chèn vào giữa 
   int index = 0;
   SimpleNode prev = null;
   SimpleNode current = myList.getHeader();
   while (index < position){
    index++;
    prev = current;
    current = current.getNext();
   }
   newNode.setNext(current);
   prev.setNext(newNode);
  }
  // Cập nhật sốlượng node của danh sách 
  myList.setNodeNumber(myList.getNodeNumber() + 1);
 }
 /* Phương thức loại bỏmột node ởvịtrí @position */
 public SimpleNode remove(int position){
  if ((myList.getNodeNumber() == 0) ||
   (position < 0) || (position >= myList.getNodeNumber()))
   return null;
  SimpleNode result = null;
  if (position == 0){ // Loại phần tử đầu 
   result = myList.getHeader();
   myList.setHeader(myList.getHeader().getNext()); if (myList.getNodeNumber() == 1) // Danh sách chỉcó 1 phần tử
    myList.setTailer(null);
  }
  else if (position == myList.getNodeNumber() - 1){ // Loại phần tửcuối 
   result = myList.getTailer();
   SimpleNode current = myList.getHeader();
   while (!current.getNext().equals(myList.getTailer()))
    current = current.getNext();
   current.setNext(null);
   myList.setTailer(current);
  }
  else{ // Loại phần tửnằm giữa danh sách 
   int index = 0;
   SimpleNode prev = null;
   SimpleNode current = myList.getHeader();
   while (index < position){
    index++;
    prev = current;
    current = current.getNext();
   }
   prev.setNext(current.getNext());
   result = current;
  }
  // Cập nhật sốlượng node của danh sách 
  myList.setNodeNumber(myList.getNodeNumber() - 1);
  result.setNext(null);
  return result;
 }
 /* Phương thức duyệt toàn bộdanh sách */
 public Node[] travese(){
  // Danh sách rỗng 
  if (myList.getNodeNumber() == 0)
   return null;
  // Danh sách không rỗng 
  Node[] result = new Node[myList.getNodeNumber()];
  SimpleNode current = myList.getHeader();
  int index = 0;
  while (current != null){
   result[index] = current.getValue();
   index++;
   current = current.getNext();
  }
  return result;
 }
}

2. Danh sách liên kết kép
a. Định nghĩa một nút của danh sách liên kết kép
Một nút của danh sách liên kết kép bao gồm:
•  Giá trịcủa nút, có dạng là một đối tượng kiểu Node đã được định nghĩa trong chương trình 1a
•  Nút tiếp theo của nút đó.
•  Nút trước của nút đó.
Một nút của danh sách liên kết kép được cài đặt trong chương trình 2a.

//Chương trình 2a
public class DoubleNode{
 private Node value;
 private DoubleNode prev;
 private DoubleNode next;
 /* Các phương thức khởi dựng */
 public DoubleNode(){
  value = new Node();
  prev = null;
  next = null;
 }
 public DoubleNode(Node value){
  this.value = value;
  prev = null;
  next = null;
 }
 /* Phương thức truy nhập thuộc tính value */
 public Node getValue(){
  return value;
 }
 public void setValue(Node value){
  this.value = value;
 }
 /* Phương thức truy nhập thuộc tính next */
 public DoubleNode getNext(){
  return next;
 }
 public void setNext(DoubleNode next){
  this.next = next;
 }
 /* Phương thức truy nhập thuộc tính prev */
 public DoubleNode getPrev(){
  return prev;
 }
 public void setPrev(DoubleNode prev){
  this.prev = prev;
 }
}

b. Định nghĩa đỉnh tiêu đề của danh sách liên kết kép
Đỉnh tiêu đề của danh sách liên kết đơn là một đối tượng khác với một nút thông thường của danh sách. Đối tượng này lưu các thông tin: • Chỉ đến nút thực sự đầu tiên của danh sách • Chỉ đến nút cuối cùng của danh sách • Lưu giữ số lượng nút thực sự trong danh sách. Chương trình 2b cài đặt lớp đỉnh tiêu đề của danh sách.

//Chương trình 2b
public class HeaderDoubleNode{
 private int nodeNumber;
 private DoubleNode header;
 private DoubleNode tailer;
 /* Phương thức khởi dựng */
 public HeaderDoubleNode(){
  nodeNumber = 0;
  header = null;
  tailer = null;
 }
 /* Phương thức truy nhập thuộc tính nodeNumber */
 public int getNodeNumber(){
  return nodeNumber;
 }
 public void setNodeNumber(int nodeNumber){
  this.nodeNumber = nodeNumber;
 }
 /* Phương thức truy nhập thuộc tính header */
 public DoubleNode getHeader(){
  return header;
 }
 public void setHeader(DoubleNode header){
  this.header = header;
 }
 /* Phương thức truy nhập thuộc tính tailer */
 public DoubleNode getTailer(){
  return tailer;
 }
 public void setTailer(DoubleNode tailer){
  this.tailer = tailer;
 }
}

c. Cài đặt danh sách liên kết kép
Danh sách liên kết kép có thuộc tính cục bộ là mộ đối tượng kiểu HeaderDoubleNode. Và có các thao tác chính:
•  Thêm một phần tử vào một vị trí bất kì: nếu vị trí nhỏ hơn 0, thêm vào đầu danh sách. Nếu vị trí lớn hơn độ dài danh sách, thêm vào cuối. Trường hợp còn lại, chèn vào danh sách một cách bình thường.
•  Loại bỏ một phần tử ở vị trí bất kì: Chỉ loại bỏ khi vị trí chỉ ra nằm trong phạm vi độ dài danh sách. Phương thức này trả về nút bị loại bỏ, có kiểu DoubleNode.
•  Duyệt toàn bộ danh sách: Trả về giá trị của tất cả các phần tử có trong danh sách. Giá trịtrả về là một mảng các phần tử giá trị có kiểu Node.
Chương trình 2c cài đặt lớp danh sách liên kết kép.

//Chương trình 2c
public class DoubleList{
 private HeaderDoubleNode myList;
 /* Các phương thức khởi dựng */
 public DoubleList(){
  myList = new HeaderDoubleNode();
 }
 /* Phương thức chèn thêm một node vào vịtrí @position */
 public void insert(Node value, int position){
  // Tạo một node mới 
  DoubleNode newNode = new DoubleNode(value);
  if (position <= 0){ // Chèn vào đầu 
   newNode.setNext(myList.getHeader());
   myList.getHeader().setPrev(newNode);
   myList.setHeader(newNode);
   if (myList.getNodeNumber() == 0) // Danh sách ban đầu rỗng 
    myList.setTailer(newNode);
  }
  else if (position >= myList.getNodeNumber()){ // Chèn vào cuối 
   if (myList.getNodeNumber() == 0){ // Danh sách ban đầu rỗng 
    myList.setHeader(newNode);
    myList.setTailer(newNode);
   }
   else{ // Danh sách không rỗng 
    newNode.setPrev(myList.getTailer());
    myList.getTailer().setNext(newNode);
    myList.setTailer(newNode);
   }
  }
  else{ // Chèn vào giữa 
   int index = 0;
   DoubleNode current = myList.getHeader();
   while (index < position){
    index++;
    current = current.getNext();
   }
   newNode.setNext(current);
   newNode.setPrev(current.getPrev());
   current.getPrev().setNext(newNode);
   current.setPrev(newNode);
  }
  // Cập nhật sốlượng node của danh sách 
  myList.setNodeNumber(myList.getNodeNumber() + 1);
 }
 /* Phương thức loại bỏmột node ởvịtrí @position */
 public DoubleNode remove(int position){
  if ((myList.getNodeNumber() == 0) ||
   (position < 0) || (position >= myList.getNodeNumber()))
   return null;
  DoubleNode result = null;
  if (position == 0){ // Loại phần tử đầu 
   result = myList.getHeader();
   myList.setHeader(myList.getHeader().getNext());
   if (myList.getHeader() != null)
    myList.getHeader().setPrev(null);
   if (myList.getNodeNumber() == 1) // Danh sách chỉcó 1 phần tử
    myList.setTailer(null);
  }
  else if (position == myList.getNodeNumber() - 1){ // Loại phần tửcuối 
   result = myList.getTailer();
   myList.setTailer(myList.getTailer().getPrev());
   myList.getTailer().setNext(null);
  }
  else{ // Loại phần tửnằm giữa danh sách 
   int index = 0;
   DoubleNode current = myList.getHeader();
   while (index < position){
    index++;
    current = current.getNext();
   }
   current.getPrev().setNext(current.getNext());
   current.getNext().setPrev(current.getPrev());
   result = current;
  }
  // Cập nhật sốlượng node của danh sách 
  myList.setNodeNumber(myList.getNodeNumber() - 1);
  result.setPrev(null);
  result.setNext(null);
  return result;
 }
 /* Phương thức duyệt toàn bộdanh sách */
 public Node[] travese(){
  // Danh sách rỗng 
  if (myList.getNodeNumber() == 0)
   return null;
  // Danh sách không rỗng 
  Node[] result = new Node[myList.getNodeNumber()];
  DoubleNode current = myList.getHeader();
  int index = 0;
  while (current != null){
   result[index] = current.getValue();
   index++;
   current = current.getNext();
  }
  return result;
 }
}