Single chain table of data structure learning

 

 

Define the Node class Node, which includes data domain data and pointer domain next.

public class Node<T> {
	//Data domain	
	public T data;
	//Pointer domain
	public Node<T> next;
	
	public Node() {
		
	}
	
   public Node(T data) {
		this.data=data;
	}
   
   public Node(T data, Node<T> next) {
       this.data = data;
       this.next = next;
   }
}

The class of linked list is defined, and a new linked list is initialized by construction method

public class LinkList<T> {
	//Head pointer
	Node<Object> head; 
	//Node number
    int size;
    /**
     * Initializing an empty list
     */
    public LinkList(){
    	this.head=new Node<Object>(null);
    	this.size=0;
    }
}

1. Insert (Object obj), insert an element into the linked list

/**
     * Insert element in linked list
     */
	
	public void insert(Object obj) {
		
		// Instantiate a node
		 Node<Object> node = new Node<>(obj);
         //If head is empty, insert data into head
         if (head == null) {
             head = node;
             return;
         }
         
         Node<Object> tmp = head;
         //Start from head to find the last node in the list
         while (tmp.next != null) {
             tmp = tmp.next;
         }
         //Insert data to the last node of the linked list
         tmp.next = node;
        //Number of nodes + 1 for each element inserted
       size++;
	}

Insert element test, call traverse() method to traverse

	public static void main(String[] args) {
		// Insert element test
		LinkList<Object> linkList = new LinkList<>();
		linkList.insert(true);
		linkList.insert(2);
		linkList.insert("aa");
		linkList.insert(7.5D);
		linkList.insert(5.5);
		linkList.insert(null);
		
		linkList.traverse();
}

//Print results
true 2 aa 7.5 5.5 null 

Here is the code for the traverse() method

	/**
     * Traversing linked list
     *
     */
    public void traverse() {
    	Node<Object> tmp = head;
        //Traverse from head
        while (tmp.next != null) {
        	System.out.print(tmp.next.data+" ");
            tmp = tmp.next;
        }
    }

2. size() to obtain the number of nodes in the linked list

/**
	 *Get the number of linked list nodes
	 */
	public int size() {
		
		return this.size;
	}

Test:

public static void main(String[] args) {
		// Insert element test
		LinkList<Object> linkList = new LinkList<>();
		linkList.insert(true);
		linkList.insert(2);
		linkList.insert("aa");
		linkList.insert(7.5D);
		linkList.insert(5.5);
		linkList.insert(null);
         	// Get the number of linked list elements
		 int size = linkList.size();
		 System.out.println("Number of linked list elements:"+size);
}

//Print results:
//Number of linked list elements: 6

3. delete(int index) delete the element of an index node in the linked list

/**
	 * Delete the element of an index node in the linked list
	 */
	public void delete(int index) {
		// Range validation
		if (index > this.size) {
			throw new IndexOutOfBoundsException();
		}
		Node<Object> temp = head;
		Node<Object> cur = head;
		// Let the temp pointer take the size index step first
		for (int i = size-index; i >0; i--) {
			temp = temp.next;
		}
		//Now the second pointer starts to walk, and when the first pointer finishes, the second pointer is located at the element to be deleted
		while (temp.next != null) {
			temp = temp.next;
			cur = cur.next;
		}
		cur.next=cur.next.next;
		size--;
	}

test

	public static void main(String[] args) {
		// Insert element test
		LinkList<Object> linkList = new LinkList<>();
		linkList.insert(true);
		linkList.insert(2);
		linkList.insert("aa");
		linkList.insert(7.5D);
		linkList.insert(5.5);
		linkList.insert(null);
        // Delete the element of the specified node
		 linkList.delete(3);
		 linkList.traverse();
}

//Print results:
true 2 aa 5.5 null 

4. deleteObj(Object obj) delete the elements specified in the linked list

/**
	 * Delete the elements specified in the linked list
	 */
	public void deleteObj(Object obj){
		//Range validation
		if(obj==null){
			throw new IllegalArgumentException();
		}
		Node<Object> temp = head;
		while(temp.next != null){
			if (temp.next.data.equals(obj)) {
				temp.next = temp.next.next;
                return;
			}
			temp = temp.next;
		}
	}

test

	public static void main(String[] args) {
		// Insert element test
		LinkList<Object> linkList = new LinkList<>();
		linkList.insert(true);
		linkList.insert(2);
		linkList.insert("aa");
		linkList.insert(7.5D);
		linkList.insert(5.5);
		linkList.insert(null);
		// Delete specified element
		 linkList.deleteObj("aa");
		 linkList.traverse();
}

//Print results:
true 2 7.5 5.5 null 

5. get(int index) gets the element of the specified node in the linked list

/**
	 * Get the element of the specified node in the linked list
	 */
	public Node<Object> get(int index){
		//Range validation
		if(index<0 || index>this.size){
			throw new IndexOutOfBoundsException();
		}
		Node<Object> tmp = head;
        //Start from head to find the last node in the list
        while (index>=0) {
            tmp = tmp.next;
            index--;
        }
		return tmp;
	}

test

	public static void main(String[] args) {
		// Insert element test
		LinkList<Object> linkList = new LinkList<>();
		linkList.insert(true);
		linkList.insert(2);
		linkList.insert("aa");
		linkList.insert(7.5D);
		linkList.insert(5.5);
		linkList.insert(null);
         // Gets the element of the specified node
		 Object obj = linkList.get(2).data;
		 System.out.println("Specify the element of the node:"+obj);
}
//Print results:
//Element of the specified node: aa

6. isEmpty() to determine whether the link list is empty

/**
	 * Sentence blank
	 * @return
	 */
	public boolean isEmpty() {
		if (size == 0) {
			return true;
		}
		return false;
	}

test

public static void main(String[] args) {
		// Insert element test
		LinkList<Object> linkList = new LinkList<>();
		linkList.insert(true);
		 boolean empty = linkList.isEmpty();
		 System.out.println("Sentence blank:"+empty);

		LinkList<Object> linkList1 = new LinkList<>();
		 boolean empty = linkList1.isEmpty();
		 System.out.println("Sentence blank:"+empty);
}

false  true

7. update(int index,Object obj) to modify the node element

/**
	 * Modify node elements   
	 */
	public void update(int index,Object obj) {
		this.get(index).data=obj;
	} 

test

	public static void main(String[] args) {
		// Insert element test
		LinkList<Object> linkList = new LinkList<>();
		linkList.insert(true);
		linkList.insert(2);
		linkList.insert("aa");
		linkList.insert(7.5D);
		
		
		// Modify the specified node element
		 linkList.update(2,900);
		 linkList.traverse();
	}

//Print results:
true 2 900 7.5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Added by hadoob024 on Fri, 06 Dec 2019 04:30:50 +0200