An example of implementing bidirectional linked lists for Java data structures
- 2020-04-01 03:08:17
- OfStack
public class DoubleNodeList<T> {
//Node class
private static class Node<T>{
Node<T> perv; //Before the node
Node<T> next; //After the node
T data; //data
public Node(T t){
this.data = t;
}
}
private Node<T> head; //Head node
private Node<T> last; //End node
private Node<T> other; //The standby node stores temporary operations
private int length; //Chain length of the table
public DoubleNodeList(){
head = new Node<T>(null);
last = head;
length = 0;
}
public DoubleNodeList(T data){
head = new Node<T>(data);
last = head;
length = 1;
}
public void add(T data){
if(isEmpty()){
head = new Node<T>(data);
last = head;
length++;
}else{
//The tail interpolation
other = new Node<T>(data);
other.perv = last;
last.next = other;
last = other;
length++;
}
}
public boolean addAfert(T data , T insertData){
other = head;
while(other != null){
if(other.data.equals(data)){
Node<T> t = new Node<T>(insertData);
t.perv = other;
t.next = other.next;
other.next = t;
//Determines whether to add a node after the last node
if(t.next==null){
last = t;
}
length++;
return true;
}
other = other.next;
}
return false;
}
public boolean addBefore(T data, T insertData){
other = head;
while(other != null){
if(other.data.equals(data)){
Node<T> t = new Node<T>(insertData);
t.perv = other.perv;
t.next = other;
other.perv.next = t;
length++;
return true;
}
other = other.next;
}
return false;
}
public T get(int index){
if(index>length || index<0){
throw new IndexOutOfBoundsException(" The index of crossing the line :"+index);
}
other = head;
for(int i=0;i<index;i++){
other = other.next;
}
return other.data;
}
public boolean set(T oldValue,T newValue){
other = head;
while(other!=null){
if(other.data.equals(oldValue)){
other.data = newValue;
return true;
}
other = other.next;
}
return false;
}
public boolean remove(T data){
other = head;
while(other != null){
if(other.data.equals(data)){
other.perv.next = other.next;
length--;
return true;
}
other = other.next;
}
return false;
}
public boolean contains(T data){
other = head;
while(other != null){
if(other.data.equals(data)){
return true;
}
other = other.next;
}
return false;
}
public T getLast(){
return last.data;
}
public T getFirst(){
return head.data;
}
public int getSize(){
return length;
}
public boolean isEmpty(){
return length==0;
}
public void clear(){
head = null;
length = 0;
}
public void printList(){
if(isEmpty()){
System.out.println(" An empty list ");
}else{
other = head;
for(int i=0;i<length;i++){
System.out.print(other.data+" ");
other = other.next;
}
System.out.println();
}
}
}