Ensure that you are logged in and have the required permissions to access the test.


5
Let’s Understand Abstraction—SortedLinkedList
Abstraction
Linked-list
C++

Abstraction is the process of hiding all but relevant data about an object in order to decrease complexity and increase efficiency.

In the previous post we understood encapsulation. Here to implement abstraction I have used Generic Type. We can pass any type of data (int, float, double, String) to our beloved SortedLinkedList.

The Node class needs the little modification where the type of data it stores is inferred by .

public class Node<T> {
  private T data;
  private Node next= null;
  public T getData() {
    return data; 
  }
  public void setData(T data) {
    this.data = data;
  }
  public Node<T> getNext() {
    return next;
  }
  public void setNext(Node<T> next) {
    this.next = next; 
  }
  @Override
  public String toString() {
    return Node [data=” + data + “]”;
  }
}

Constructors

@ default constructor
public SortedLinkedList() {}
@parameterized constructor
public SortedLinkedList(T[] arr) {
  for (int i = 0; i < arr.length; i++) {
    insertData(arr[i]);
  }
}

Second step to write createNode() method.

private Node<T> createNode(T data) {
  Node<T> newnode = new Node<T>();
  newnode.setData(data);
  return newnode;
}

Previously to insert data we were using comparison operators (>=, ==). For any object who needs to be compare needs Comparable interface.

public void insertData(T data) {
  Node<T> newnode = createNode(data);
  if (head == null) {
    head = newnode;
  } else {
    Node<T> node = head;
    do {
      if (node.getData().compareTo(newnode.getData()) >= 0
      && node == head) {
        newnode.setNext(head);
        head = newnode;
        break;
      } else if (node.getNext() == null
      || (((Comparable<T>) node.getNext().getData())
      .compareTo(data) >= 0)) {
        newnode.setNext(node.getNext());
        node.setNext(newnode);
        break;
      } else {
        node = node.getNext();
      }
    } while (node != null);
  }
  size++;
}

To insert array in LinkedList

public void insertData(T elements[]) {
  for (int i = 0; i < elements.length; i++) {
    insertData(elements[i]);
  }
}

Here comes the indexOf() method:

public int indexOf(T ele) {
  int position = -1;
  if (head == null) {
    System.out.println(“Linked list is empty”);
  } else {
    int i = 0;
    Node<T> node = head;
    do {
      i++;
      if (node.getData().compareTo(ele) == 0) {
        position = i;
        break;
      }
      node = node.getNext();
    } while (node != null);
  }
  return position;
}

Similarly here comes the lastIndexOf() method.

public int lastIndexOf(T ele) {
  int position = -1;
  if (head == null) {
    System.out.println(“Linked list is empty”);
  } else {
    int i = 0;
    Node<T> node = head;
    do {
      i++;
      if (node.getData().compareTo(ele) == 0) {
        position = i;
      }
      node = node.getNext();
   } while (node != null);
  }
  return position;
}

Remove element from Linked List, if list contains duplicate elements it will remove first occurrence of an element. The function also returns true/false indicating whether element is removed or not.

public boolean remove(T ele) {
  if (head != null) {
    Node<T> node = head;
    do {
      if (head.getData().compareTo(ele) == 0) {
        head = head.getNext();
        return true;
      }
      if (((Comparable<T>)node.getNext().getData())
      .compareTo(ele) == 0) {
        node.setNext(node.getNext().getNext());
        size—;
        return true;
      }
      node = node.getNext();
    } while (node != null);
  }
  return false;
}

Remove element from Linked List, if list contains duplicate elements it will remove all occurrence of an element.

public void removeAll(T ele) {
  if (head == null) {
    System.out.println(“Linked list is empty”);
  } else {
    int i = 0;
    Node<T> node = head;
    do {
      if (head.getData().compareTo(ele) == 0) {
        head = head.getNext();
        size--;
        i = 1;
      } else if (((Comparable<T>) node.getNext().getData())
      .compareTo(ele) == 0) {
        node.setNext(node.getNext().getNext());
        size--;
        i = 1;
      }
      if (i == 1) {
        i = 0;
      } else {
        node = node.getNext();
      }
    } while (node.getNext() != null);
  }
}

Last step to access SortedLinkedList class.

public static void main(String[] args) {
  Integer arr[] = { 5, 6, 8, 3, 2 };
  SortedLinkedList<Integer> list1 = new  SortedLinkedList<Integer>(arr);
  list1.insertData(30);
  System.out.println(“First Index of 8 :  + list1.indexOf(8));
  System.out.println(“Last Index of 8:“+  list1.lastIndexOf(8));
  list1.remove(5);
  list1.removeAll(2);
  list1.traversal();
  System.out.println(“Size : “+list1.size());
  list1.clear();

  String s[] = {“abc”, cde”, yoj”,”kkk”};
  SortedLinkedList<String> list2 = new SortedLinkedList<String> (s);
  list2.traversal();
  list2.insertData(“hjjh”);
  list2.insertData(“555");  
  System.out.println(“First Index of abc : “ + 
  list2.indexOf(“abc”));
  list2.remove(“cde”);
  list2.removeAll(“kkk”);
}

Benefits of bringing abstraction

  1. Our SortedLinkedList is a example of data type abstraction. You are free to use any datatype which is comparable.
  2. Makes our data structure re-usable.
  3. Write less, convey more!

Happy Coding…

Author

?