linkedlist - Connect2java

How to reverse a linked list in java using iterative

Write a program to reverse a LinkedList in Java using iterative. Solution: 1) Traverse through the linked list 2) Assign as below in loop next=prev; prev=current; current=next;



package datastructure;

public class LinkedListTest6 {	
	     

	public static void main(String[] args) {
		 
		LinkedList	linkedList = new LinkedList();    	
   	    
		linkedList.addElement( new LinkedList.Node("1"));
        linkedList.addElement( new LinkedList.Node("2"));
        linkedList.addElement( new LinkedList.Node("3"));
        linkedList.addElement( new LinkedList.Node("4"));
        linkedList.addElement( new LinkedList.Node("5"));
        linkedList.addElement( new LinkedList.Node("6"));
        linkedList.addElement( new LinkedList.Node("7"));

        reverse(linkedList);   
       
	}

	private static void displayLinkedListNodes(LinkedList.Node node) {			
						
		while(node!=null && node.getNext()!=null){
			
			System.out.println(node.element());
			node=node.getNext();
		}   	
	   
	}

	private static void reverse(LinkedList linkedList) {
		
	LinkedList.Node prevNode = null;
    LinkedList.Node currNode = linkedList.getHeaderElement();
    LinkedList.Node nextNode =null;
	
				
	  while (currNode != null )
	  {
		  nextNode=currNode.getNext();
		  currNode.next =prevNode;
		  prevNode=currNode;
		  currNode=nextNode;    		
	  }
	
	System.out.println("Displaying linked list nodes after reversing ");
	displayLinkedListNodes(prevNode);
}		
	
	
}
class LinkedList{
   private Node headerElement;
   private Node tailorElement;
 
   public LinkedList(){
       this.headerElement = new Node("HeaderElement");
       tailorElement = headerElement;
   }
 
   public Node getHeaderElement(){
       return headerElement;
   }
 
   public void addElement(Node node){
   	tailorElement.next = node;
   	tailorElement = node;
   }
 
 
   public static class Node{
       Node next;
       private String value;

       public Node(String value){
           this.value = value;
       }
     
       public String element() {
           return value;
       }

       public Node getNext() {
           return next;
       }
     
       public String toString(){
           return this.value;
       }
       public void setNext(Node next){
    	   this.next = next;
       }
   }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

package datastructure;

public class LinkedListTest6 {

public static void main(String[] args) {

LinkedList linkedList = new LinkedList();

linkedList.addElement( new LinkedList.Node("1"));

linkedList.addElement( new LinkedList.Node("2"));

linkedList.addElement( new LinkedList.Node("3"));

linkedList.addElement( new LinkedList.Node("4"));

linkedList.addElement( new LinkedList.Node("5"));

linkedList.addElement( new LinkedList.Node("6"));

linkedList.addElement( new LinkedList.Node("7"));

reverse(linkedList);

}

private static void displayLinkedListNodes(LinkedList.Node node) {

while(node!=null && node.getNext()!=null){

System.out.println(node.element());

node=node.getNext();

}

private static void reverse(LinkedList linkedList) {

LinkedList.Node prevNode = null;

LinkedList.Node currNode = linkedList.getHeaderElement();

LinkedList.Node nextNode =null;

while (currNode != null )

{

nextNode=currNode.getNext();

currNode.next =prevNode;

prevNode=currNode;

currNode=nextNode;

}

System.out.println("Displaying linked list nodes after reversing ");

displayLinkedListNodes(prevNode);

}

class LinkedList{

private Node headerElement;

private Node tailorElement;

public LinkedList(){

this.headerElement = new Node("HeaderElement");

tailorElement = headerElement;

}

public Node getHeaderElement(){

return headerElement;

}

public void addElement(Node node){

tailorElement.next = node;

tailorElement = node;

}

public static class Node{

Node next;

private String value;

public Node(String value){

this.value = value;

}

public String element() {

return value;

}

public Node getNext() {

return next;

}

public String toString(){

return this.value;

}

public void setNext(Node next){

this.next = next;

}

Output:



Displaying linked list nodes after reversing 
7
6
5
4
3
2
1

1

2

3

4

5

6

7

8

9

10

11

12

Displaying linked list nodes after reversing

7

6

5

4

3

2

1

How to find/detect infinite loop of linked list in java

There are multiple solutions to solve this. But we will discuss Floyd’s Cycle-Finding Algorithm. This algorithm also called as “Tortoise and Hare Algorithm”. Solution: 1) Initialize 2 pointers called fast and slow with header element. Move slow pointer by one element and fast pointer by two elements 2) If these 2 pointers meet at some […]

Find the Nth node/element from a LinkedList in java

You have given a LinkedList (not java.util.LinkedList), and a number N. Write a program to find/print the value at the Nth node from a LinkedList in Java. Solution: 1) Initialize length to zero 2) Traverse through the list If length is equal to the passed index, return current element Increment length Assign current element to […]

Find middle node/element of a LinkedList in Java

Write a program to find/print middle element of a Linked list in Java using length of a linked list Solution: 1) Find the length of linked list. 2) Print the middle of a linked list at (length/2) th node/element.



public class LinkedListTest {

	public static void main(String[] args) {
		
		LinkedList linkedList = new LinkedList();    	
   	    linkedList.addElement( new LinkedList.Node("1"));
        linkedList.addElement( new LinkedList.Node("2"));
        linkedList.addElement( new LinkedList.Node("3"));
        linkedList.addElement( new LinkedList.Node("4"));
        linkedList.addElement( new LinkedList.Node("5"));
        linkedList.addElement( new LinkedList.Node("6"));
        linkedList.addElement( new LinkedList.Node("7"));
        linkedList.addElement( new LinkedList.Node("8"));
        linkedList.addElement( new LinkedList.Node("9"));
        printMiddleElement(linkedList);
	}

	private static void printMiddleElement(LinkedList linkedList) {
		
		
		LinkedList.Node node = linkedList.getHeaderElement();
		int length=0;
		
		// 1) count the number of nodes/elements in LinkedList
		while(node.next()!=null){
			length++;
			node=node.next();
		}
		
	   node=linkedList.getHeaderElement();
	   
	// 2) Get the (lenght/2)th node from the starting
	    for (int i = 1; i <= length/2; i++)
	       node=node.next();
	    
  System.out.println("Middle element of linked list is " + node.next().value());
		
	}
}
class LinkedList{
    private Node headerElement;
    private Node tailorElement;
  
    public LinkedList(){
        this.headerElement = new Node("HeaderElement");
        tailorElement = headerElement;
    }
  
    public Node getHeaderElement(){
        return headerElement;
    }
  
    public void addElement(Node node){
    	tailorElement.next = node;
    	tailorElement = node;
    }
  
  
    public static class Node{
        private Node next;
        private String value;

        public Node(String value){
            this.value = value;
        }
      
        public String value() {
            return value;
        }

        public Node next() {
            return next;
        }
      
        public String toString(){
            return this.value;
        }
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

public class LinkedListTest {

public static void main(String[] args) {

LinkedList linkedList = new LinkedList();

linkedList.addElement( new LinkedList.Node("1"));

linkedList.addElement( new LinkedList.Node("2"));

linkedList.addElement( new LinkedList.Node("3"));

linkedList.addElement( new LinkedList.Node("4"));

linkedList.addElement( new LinkedList.Node("5"));

linkedList.addElement( new LinkedList.Node("6"));

linkedList.addElement( new LinkedList.Node("7"));

linkedList.addElement( new LinkedList.Node("8"));

linkedList.addElement( new LinkedList.Node("9"));

printMiddleElement(linkedList);

}

private static void printMiddleElement(LinkedList linkedList) {

LinkedList.Node node = linkedList.getHeaderElement();

int length=0;

// 1) count the number of nodes/elements in LinkedList

while(node.next()!=null){

length++;

node=node.next();

}

node=linkedList.getHeaderElement();

// 2) Get the (lenght/2)th node from the starting

for (int i = 1; i <= length/2; i++)

node=node.next();

System.out.println("Middle element of linked list is " + node.next().value());

}

class LinkedList{

private Node headerElement;

private Node tailorElement;

public LinkedList(){

this.headerElement = new Node("HeaderElement");

tailorElement = headerElement;

}

public Node getHeaderElement(){

return headerElement;

}

public void addElement(Node node){

tailorElement.next = node;

tailorElement = node;

}

public static class Node{

private Node next;

private String value;

public Node(String value){

this.value = value;

}

public String value() {

return value;

}

public Node next() {

return next;

}

public String toString(){

return this.value;

}

Output:



Middle element of linked list is 5

1

2

3

4

5

Middle element of linked list is 5

Find middle node/element of a LinkedList in Java in one pass.

Write a program to find/print middle element of a Linked list in Java in one pass. Solution: 1) Initialize 2 pointers called fast and slow with header element. Move slow pointer by one element and fast pointer by two elements 2) Once the fast pointer reaches end, then slow pointer will reach middle of a […]

Find Nth node/element from the end of a LinkedList in java

You have given a LinkedList (not java.util.LinkedList), and a number N. Write a program to find/print the value at the Nth node from end of a LinkedList in Java. Solution1 (Using length of a LinkedList): 1) Find the length of linked list. 2) Print the (length-n+1) th node/element from starting of the linked list.



public class LinkedListTest {
    public static void main(String[] args) {
        
         LinkedList linkedList = new LinkedList();        
         linkedList.addElement( new LinkedList.Node("1"));
         linkedList.addElement( new LinkedList.Node("2"));
         linkedList.addElement( new LinkedList.Node("3"));
         linkedList.addElement( new LinkedList.Node("4"));
         linkedList.addElement( new LinkedList.Node("5"));
         linkedList.addElement( new LinkedList.Node("6"));
         linkedList.addElement( new LinkedList.Node("7"));
         
         printNthElementFromLast(linkedList,5);
    }
 
    private static void printNthElementFromLast(LinkedList linkedList, int pos) {
        
        LinkedList.Node node = linkedList.getHeaderElement();
        int length=0;
        
        // 1) count the number of nodes/elements in LinkedList
        while(node.next()!=null){
            length++;
            node=node.next();
        }
        
        // check if value of n is not more than length of the linked list
       if (length < pos){
        System.out.println( "The " + pos + "th position which you want to see " +
                            "from last is not there, " +"becuase "+pos+" is " +
                            "greater than the number of elements/nodes in the list");
            return;
        }
        
        node=linkedList.getHeaderElement();
        
     // 2) Get the (n-length+1)th node from the starting
        for (int i = 1; i <= length-pos+1; i++)
           node=node.next();
        
        System.out.println("Node/Element number " + pos +" from last is " 
                            +node.value());
                
    }
 
}
class LinkedList{
    private Node headerElement;
    private Node tailorElement;
  
    public LinkedList(){
        //Don't consider "HeaderElement" as element in LinkedList
        this.headerElement = new Node("HeaderElement"); 
        tailorElement = headerElement;
    }
  
    public Node getHeaderElement(){
        return headerElement;
    }
  
    public void addElement(Node node){
        tailorElement.next = node;
        tailorElement = node;
    }
  
  
    public static class Node{
        private Node next;
        private String value;
 
        public Node(String value){
            this.value = value;
        }
      
        public String value() {
            return value;
        }
 
        public Node next() {
            return next;
        }
      
        public String toString(){
            return this.value;
        }
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

public class LinkedListTest {

public static void main(String[] args) {

LinkedList linkedList = new LinkedList();

linkedList.addElement( new LinkedList.Node("1"));

linkedList.addElement( new LinkedList.Node("2"));

linkedList.addElement( new LinkedList.Node("3"));

linkedList.addElement( new LinkedList.Node("4"));

linkedList.addElement( new LinkedList.Node("5"));

linkedList.addElement( new LinkedList.Node("6"));

linkedList.addElement( new LinkedList.Node("7"));

printNthElementFromLast(linkedList,5);

}

private static void printNthElementFromLast(LinkedList linkedList, int pos) {

LinkedList.Node node = linkedList.getHeaderElement();

int length=0;

// 1) count the number of nodes/elements in LinkedList

while(node.next()!=null){

length++;

node=node.next();

}

// check if value of n is not more than length of the linked list

if (length < pos){

System.out.println( "The " + pos + "th position which you want to see " +

"from last is not there, " +"becuase "+pos+" is " +

"greater than the number of elements/nodes in the list");

return;

}

node=linkedList.getHeaderElement();

// 2) Get the (n-length+1)th node from the starting

for (int i = 1; i <= length-pos+1; i++)

node=node.next();

System.out.println("Node/Element number " + pos +" from last is "

+node.value());

}

class LinkedList{

private Node headerElement;

private Node tailorElement;

public LinkedList(){

//Don't consider "HeaderElement" as element in LinkedList

this.headerElement = new Node("HeaderElement");

tailorElement = headerElement;

}

public Node getHeaderElement(){

return headerElement;

}

public void addElement(Node node){

tailorElement.next = node;

tailorElement = node;

}

public static class Node{

private Node next;

private String value;

public Node(String value){

this.value = value;

}

public String value() {

return value;

}

public Node next() {

return next;

}

public String toString(){

return this.value;

}

[…]

ArrayList,LinkedList,Vector and Stack

ArrayList (Since Java 1.2): Grow able Array implementation of List interface. Insertion order is preserved. Duplicate elements are allowed. Multiple null elements of insertion are allowed. Default initial capacity of an ArrayList is 10. The capacity grows with the below formula, once ArrayList reaches its max capacity. newSize/newCapacity= (oldCapacity * 3)/2 + 1



package com.c2j.collectionframework.list;

import java.util.ArrayList;

public class ArrayListExample {
	
	public static void main(String[] args) {
		
		ArrayList arrayList = new ArrayList();
		
		arrayList.add("Sreenath");
		arrayList.add("Sreenath");
		arrayList.add(10.5);
		arrayList.add(25);
		arrayList.add(null);
		arrayList.add(null);
		System.out.println(arrayList);		
	}
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

package com.c2j.collectionframework.list;

import java.util.ArrayList;

public class ArrayListExample {

public static void main(String[] args) {

ArrayList arrayList = new ArrayList();

arrayList.add("Sreenath");

arrayList.add(10.5);

arrayList.add(25);

arrayList.add(null);

System.out.println(arrayList);

}

Output: […]