Singly Linked List in java
#techlearners #java #linkedlist
Linked list is a linear collection of data elements, called nodes pointing to the next node by means of pointers
Each node is divided into two parts
First part - containing the information
Second part - containing the address of next node in the list
info Link
45 null
Need of linked lists
1. Overcome the drawback of arrays as number of elements need not be predetermined
2. More memory can be allocated and released during the
processing
3. Insertion and deletion much easier and simpler
Example of linked list
START 10 Link --- 25 Link --- 43 null
Types of linked lists
1 Singly linked list
2 Doubly linked list
Singly Linked List
1. The list has a header reference that points to first node
it is called START
2. List has a sequence of nodes
3. Each node consist of a value and a link pointing to next node
4. The last node contains a null link
Basic Operations on linked list
1 Insertion
a. In Sorted List
b. In Unsorted List
2 Deletion
3 Searching
4 Traversing
5 Concatenation
6 Splitting
7 Reversal
a. Creating a new reversed List
b. Reversing the nodes of the same list
Singly Linked List
1. Create a class Node which has two attributes: data and next. Next is a pointer to the next node.
2. Create another class which has two attributes: head and tail.
3. addNode() will add a new node to the list:
a. Create a new node.
10 null
b. It first checks, whether the head is equal to null which means the list is empty.
c. If the list is empty, both head and tail will point to the newly added node.
d. If the list is not empty, the new node will be added to end of the list such that tail's next will point to the newly added node. This new node will become the new tail of the list.
4. display() will display the nodes present in the list:
5. Define a node current which initially points to the head of the list.
6. Traverse through the list till current points to null.
7. Display each node by making current to point to node next to it in each iteration.
