Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Singly linked list
- */
- package linkedlisttest;
- class Node {
- int data;
- Node next;
- public Node(int data) {
- this.data = data;
- }
- }
- class LinkedList {
- Node head;
- int size;
- /**
- *
- * @param data element to add to list
- * Time Complexity : O(n)
- */
- public void add(int data) {
- if (head == null) {
- head = new Node(data);
- size += 1;
- return;
- }
- Node current = head;
- while (current.next != null) {
- current = current.next;
- }
- current.next = new Node(data);
- size += 1;
- }
- /**
- *
- * @return size of list
- * Time Complexity: O(1)
- * This is because we use a class
- * variable size to keep track of size of linked list
- */
- public int getSize() {
- return size;
- }
- /**
- *
- * @param data element to insert
- * @param index position at which to insert the element (zero based)
- * Time Complexity : O(n)
- */
- public void add(int data, int index) {
- if (index > getSize()) {
- return; // invalid position
- }
- Node current = head; //iterate through whole list
- int pos = 0;
- Node newNode = new Node(data);
- if (index == 0) // special case, since its a single reference change!
- {
- newNode.next = head;
- head = newNode; // this node is now the head
- size += 1;
- return;
- }
- while (current.next != null) {
- if (pos == index - 1) {
- break;
- }
- pos++;
- current = current.next;
- }
- // These are 2 reference changes, as compared to adding at index 0
- newNode.next = current.next; // here we are changing a refernce
- current.next = newNode; // changing a reference here as well
- size += 1;
- }
- /**
- * Find the first occurrence of an element
- * @param data element to find
- * @return index at which element is found , -1 if not exist
- * Time Complexity: O(n)
- */
- public int find(int data) {
- Node current = head;
- int pos = 0;
- int index = -1;
- if(head == null) { //empty list
- return index;
- }
- while(current != null) {
- if (current.data == data) {
- index = pos;
- break;
- }
- pos++;
- current = current.next;
- }
- return index;
- }
- /**
- * Delete the first occurrence of data
- * @param data element to delete
- * Time complexity : O(n)
- */
- public void delete(int data) {
- Node current = head;
- if (head == null) { // list is empty
- return;
- }
- if(head.data == data) { // if we want to delete the head , make next node head
- head = head.next;
- size -= 1;
- return;
- }
- while(current.next != null) {
- if (current.next.data == data) {
- current.next = current.next.next;
- size -= 1;
- return;
- }
- current = current.next;
- }
- }
- /**
- * Delete all occurrences of data
- * @param data element to delete
- *
- */
- public void deleteAll(int data) {
- Node current = head;
- if (head == null) { // list is empty
- return;
- }
- //while loop to delete consecutive occurances of data
- while(head.data == data) { // if we want to delete the head , make next node head
- head = head.next;
- size -= 1;
- }
- while(current.next != null) {
- //while loop to delete consecutive occurances of data
- while (current.next.data == data) {
- current.next = current.next.next;
- size -= 1;
- }
- current = current.next;
- }
- }
- public void reverse() {
- }
- /**
- * Prints the whole linked list
- * Time Complexity : O(n)
- */
- public void print() {
- if(head == null) { //list is empty
- return;
- }
- Node current = head;
- while (current.next != null) {
- System.out.print(current.data + "->");
- current = current.next;
- }
- System.out.print(current.data + "n");
- }
- }
- public class LinkedListTest {
- /**
- * @param args the command line arguments
- */
- public static void main(String[] args) {
- LinkedList lt = new LinkedList();
- lt.print();
- lt.add(3);
- lt.add(5);
- lt.add(6);
- lt.print();
- lt.add(4, 1);
- lt.print();
- lt.add(4, 7);// 7 is an invalid index
- lt.add(8, 3);
- lt.add(8, 4);
- lt.print();
- System.out.println("Position : " + lt.find(8));
- lt.delete(5);
- lt.print();
- lt.deleteAll(8);
- lt.print();
- System.out.println("Size : " + lt.getSize());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement