Java связанный список. Операция delete на примерах.

Класс связанный список в Java (linked list) — это коллекция, которая может содержать множество объектов одного типа, как и ArrayList.

Класс в Java связанный список имеет все те же методы, что и класс ArrayList, поскольку оба они реализуют интерфейс List. Это означает, что вы можете добавлять элементы, изменять элементы, удалять элементы и очищать список таким же образом.

Класс связанный список реализует и формирует основу для многих других структур данных, некоторые из которых включают список, очередь, Стек и Deque.

@javatg – Java в телеграме.

Плюсы связанного списка перед массивами

Редактирование связных элементов осуществляется за постоянное время (0(1)), не как в массивах. Связанный список просто расширять, просто добавив элемент.

Перед использованием соответствующей составляющей языка важно помнить: для поиска элемента требуется каждый раз проходить весь список. Время доступа к искомому = O (n).

Узлы в связанном списке

Немного теории о узлах.

Новый узел – это элемент, который содержит информацию, подлежащую дальнейшему сохранению, а также указатель на следующий элемент или значение NULL, если рассматриваемая «часть» является последней.

Перейдем к практике по работе со связанным списком!

Удаляем первый узел

Java связанный список. Операция delete на примерах.
//delete first node method 
 //delete first node
    public void deleteFirstNode(){
        if(isEmpty()){
            System.out.println("Linked list is empty");
        }
        else{
            Node<T> tempNode=head;
            head=tempNode.nextNode;
            tempNode.nextNode=null;
            tail=getTail();
            size--;
            // System.out.println(head.data+" is deleted.");       
        }
    }

Удаляем последний узел

Java связанный список. Операция delete на примерах.
//delete last node method 
public void deleteLastNode(){
        if(isEmpty()){
            System.out.println("Underflow condition : Linked list is empty");
        }
        else{
            Node<T> tempNode=head;
            for(int i=1; i<size-1; i++){
                tempNode=tempNode.nextNode;
            }
            tempNode.nextNode=null;
            tail=tempNode;
            size--;
        }
    }

Удаляем узел в заданной позиции в связанном списке

Java связанный список. Операция delete на примерах.
//delete a node at a given position
public void deteleAtAnyPos(int pos){
        if(pos==1){
            deleteFirstNode();
        }
        else if(pos>=size){
            deleteLastNode();
        }
        else if(pos>1 && pos<size){
            Node<T> tempNode=head;
            for(int i=1; i<pos-1; i++){
                tempNode=tempNode.nextNode;
            }
            // System.out.println(tempNode.nextNode.data+" is deleted.");
            tempNode.nextNode=tempNode.nextNode.nextNode;
            size--;
        }
    }

Удалить по значению

    //Delete by a given value
    public void deleteByValue(T data){
        int nodeNum=searchValue(data);
        if(nodeNum!=0){
            deteleAtAnyPos(nodeNum);
        }
    }

Полный код по работе со связанным списком на Java

//Main class
public class Main {
    public static void main(String[] args) {
      //linked list
      linkedList<String> Students=new linkedList<>();
      String[] studentsList={"StudentA","StudentB","StudentC","StudentD","StudentE"};
      for(String i : studentsList){
        Students.insertAtLast(i);
      }
      //Let's us display the list of students 
      System.out.println("21SW students list");
      Students.display();
      Students.deleteByValue("StudentC");
      System.out.println("After deleting element StudentC");
      Students.display();
      Students.deleteFirstNode();
      System.out.println("Students list after deleting first node : ");
      Students.display();
      Students.deleteLastNode();
      System.out.println("Students list after deleting last node");
      Students.display();
      Students.deteleAtAnyPos(2);
      System.out.println("Students list after deleting element at pos : 2");
      Students.display();

    }
}

//Singly Linked list class 
class linkedList<T>{ 
   //Nested node class; it is a static class
   static class Node<L>{
    //proeprties
    L data;
    Node<L> nextNode;
    Node(L data){
        this.data=data;
        nextNode=null;
    }
   }
   //linked list class properties/Data members
   int size;
   Node<T> head, tail;
   //constructor; initialized the default values
   linkedList(){
    size=0;
    head=null;
    tail=null;
   }
   public Node<T> getTail() {
        Node<T> tempNode=head;
        while(tempNode.nextNode!=null){
            tempNode=tempNode.nextNode;
        }
        tail=tempNode;
        return tail;
    }
    //isEmpty method
    public boolean isEmpty(){
        if(size==0)
            return true;
        else
            return false;
    }
    // Size method
    public int sizeOfLinkedList(){
        return size;
    }
    // insertAtLast method
    public void insertAtLast(T data){
        Node<T> newNode=new Node<T>(data);//create a new node to be inserted at last
        //if linked list is empty than call insert at first method
        if(isEmpty()){
            insertAtFirst(data);
        }
        else{
            getTail().nextNode=newNode;
            size++;
            // System.out.println(data+" is inserted.");
        }  
    }
    
    //delete first node
    public void deleteFirstNode(){
        if(isEmpty()){
            System.out.println("Linked list is empty");
        }
        else{
            Node<T> tempNode=head;
            head=tempNode.nextNode;
            tempNode.nextNode=null;
            tail=getTail();
            size--;
            // System.out.println(head.data+" is deleted.");       
        }
    }
   //delete last node
    public void deleteLastNode(){
        if(isEmpty()){
            System.out.println("Underflow condition : Linked list is empty");
        }
        else{
            Node<T> tempNode=head;
            for(int i=1; i<size-1; i++){
                tempNode=tempNode.nextNode;
            }
            tempNode.nextNode=null;
            tail=tempNode;
            size--;
        }
    }
    //delete node at any position
    public void deteleAtAnyPos(int pos){
        if(pos==1){
            deleteFirstNode();
        }
        else if(pos>=size){
            deleteLastNode();
        }
        else if(pos>1 && pos<size){
            Node<T> tempNode=head;
            for(int i=1; i<pos-1; i++){
                tempNode=tempNode.nextNode;
            }
            // System.out.println(tempNode.nextNode.data+" is deleted.");
            tempNode.nextNode=tempNode.nextNode.nextNode;
            size--;
        }
    }
    //Delete by a given value
    public void deleteByValue(T data){
        int nodeNum=searchValue(data);
        if(nodeNum!=0){
            deteleAtAnyPos(nodeNum);
        }
    }
    //Search method 
    public int searchValue(T data){
            Node<T> tempNode=head;
            int nodeNum=0;
            //search node if it exists return it 
            if(isEmpty()){
                System.out.println("Linked list is empty");
                return nodeNum;
            }        
            else{
                while(tempNode!=null){
                    nodeNum++;
                    if(tempNode.data==data){
                        break;
                    }
                    else{
                        tempNode=tempNode.nextNode;
                    }
                }
               return nodeNum; 
            }
           
        }
}

Спасибо за внимание! Связанный список в Java это очень удобная и полезная структура, в следующих статьях мы рассмотрим другие операции.

+1
0
+1
0
+1
0
+1
0
+1
1

Ответить

Ваш адрес email не будет опубликован. Обязательные поля помечены *