Introduction and usage of singly linked list in java

Singly linked list:
* 1. The linked list can be an ordered or unordered list
* 2. The contents of the linked list are usually stored in memory until they are dispersed
* 3. The linked list consists of nodes Composed, each node has the same structure
* 4. The node is divided into data domain and chain domain. The data domain stores the node content, and the chain domain stores the pointer of the next node

package myLinkList;

public class MyLinkedList {

/**
*Node: Node object
* Including data field data and link field next (pointing to the next node object)
*/
class Node {
　private T data;
　private Node next;
　public Node( ){

 }
 //Node initialization
 public Node(T data,Node next){
  this.data = data;
  this.next = next;
}
}

private Node header;//Linked list head node
private Node tailer;//Linked list tail node
private int size;//Linked list length (number of nodes)


/**
* Linked list initialization
*/
public MyLinkedList() {//Empty parameter construction
　header = null;
　tailer = null;
}
public MyLinkedList(T data) {//Construction with parameters
header = new Node(data,null);//Create header node
tailer = header;
size++;
}

/**
* Find the length of the linked list
* @return
*/
public int getSize() {
　return size;
}

/**
* Return the data of the node with index index
* @param index index
* @return
*/
public T get( int index) {
　if(index < 0 || index > size-1)
　　throw new IndexOutOfBoundsException("index out of bounds");
　　return getIndexNode(index).data;
}

public Node getIndexNode(int index){
　if(index < 0 || index > size-1)
　　throw new IndexOutOfBoundsException("index out of bounds");
　Node current = header;
　for(int i = 0;i < size; i++) {
　　if(i == index) {
　　return current;
　　}
　　current = current.next ;
}
　 return null;
}

/**
* Returns the position of element in the linked list. If it does not exist, returns -1
* @param tdata
* @return
*/
public int getIndex(T element) {
　if(element == null)
　　return -1;
　Node current = header;
　for(int i = 0; i < size; i++) {
　　if(current.data == element){
　　return i;
 }
 current = current.next;
}
 return -1;
}



/**
* Add element
at the end of the linked list * @param element
*/
public void add(T element) {
　Node n = new Node(element,null);
　if(header == null){
　header = n;
　tailer = header;
}else{
　tailer.next = n;
　tailer = n;
}
　size++;
}

/**
* Add element
at the head of the linked list * @param element
*/
public void addAtheader(T element) {
　header = new Node(element,header);
　if(tailer == null){
　　tailer = header;
　　}
　size++;
}

/**
* Insert element after index position
* @param index
* @param element
*/
public void insert(int index,T element) {
　if(index<0 || index>size-1) {
　　throw new IndexOutOfBoundsException("index out of bounds");
　　}
　if(header==null){
　　add(element);
　　}else{
　　if(index==0 ){
　　addAtheader (element); insertNode;
　　　　size++;
　　　}
　　}
}
/**
* Delete the node at any position
* @param index
* @return
*/
public T deleteNode(int index){
　if(index<0 | | index>size-1)
　　throw new IndexOutOfBoundsException("index out of bounds");
　if(index == 0){//Delete element in the head
　　Node n = header;//Record header Node
　header = header.next;//Point the head pointer to the next node
　　size--;
　　return n.data;//Output the contents of the record node
　　}else{//In Delete at other locations
　　Node current = getIndexNode(index);//Get the current node
　　Node pre = getIndexNode(index-1);//Get the previous node
　　pre.next = current.next;/ /Set the chain field of the previous node to null
　　size--;
　　return current.data;//Return the data field of the deleted node
　　}


}
/**
* Delete the head node
* @return
*/
public T deleteHeader(){
 return deleteNode(0);
}
/**
* Delete the tail node
* @return
*/
public T deleteTailer() {
return deleteNode(size-1);
}

//Clear the node
public void clear(){
　　header = null;
　　tailer = null;
　　size = 0;
}

/**
* toString();
*/
public String toString(){
　　if(size == 0)
　　　　return "[]";
　　Node current = header;
　　StringBuilder sb = new StringBuilder();
　　sb.append("[");
　　while(current.next != null) {
　　　　sb.append(current.data).append("  ");
　　　　current = current.next;
　　}
　　sb.append(current.data).append("]");
　　return sb.toString();
}


public static void main(String[] args) {
　　MyLinkedList link = new MyLinkedList<>();
　　link.add("header");
　　link.add("11");
　　link.add("22");
　　link.add("33");
　　link.addAtheader("newheader");
　　link.insert(2, "1.5");;

　　System.out.println(link.getIndex("11"));
　　System.out.println(link.getIndex("88"));
　　System.out.println(link.get(0));
　　System.out.println(link.getSize());
　　System.out.println(link.deleteHeader());
　　System.out.println(link.deleteTailer());
　　System.out.println(link.deleteNode(1));
　　System.out.println(link);
　　link.clear();
　　System.out.println(link);

　　}

}

The above is the detailed content of Introduction and usage of singly linked list in java. For more information, please follow other related articles on the PHP Chinese website!