Linked list Data Structure

 A linked list is a linear data structure where elements, called nodes, are connected using pointers. Each node in a linked list contains two parts:

Value: Holds the value/data for the Node.

Next (pointer): Holds a reference (pointer) to the next Node.

The head is the first node in the linked list. It is the starting point for traversal through the list. 

The tail is the last node in the linked list.

This table describes the worst-case time complexities of various operations on a linked list.

1. Append (O(1))

• Operation: Add an item to the end of the list.
• Reason: If a reference to the tail node is maintained, appending is constant time because you only update the next pointer of the tail.

2. Remove Last (O(n))

• Operation: Remove the last item from the list.
• Reason: In a singly linked list, you need to traverse the entire list to find the second-to-last node to update its next pointer to null. This traversal takes linear time.

3. Prepend (O(1))

• Operation: Add an item to the beginning of the list.
• Reason: You only need to update the head pointer to point to the new node, which takes constant time.

4. Remove First (O(1))

• Operation: Remove the first item from the list.
• Reason: You simply update the head pointer to point to the next node, which is a constant-time operation.

5. Insert (O(n))

• Operation: Insert an item at a specific position in the list.
• Reason: You need to traverse the list to find the insertion point, which takes linear time.

6. Remove (O(n))

• Operation: Remove an item at a specific position in the list.
• Reason: You need to traverse the list to find the node just before the one being removed, which takes linear time.

7. Lookup by Index (O(n))

• Operation: Access an item at a specific index.
• Reason: Unlike arrays, linked lists do not have direct indexing. You must traverse the list from the beginning to locate the node at the specified index.

8. Lookup by Value (O(n))

• Operation: Find an item by its value.
• Reason: You must traverse the entire list to compare each node's value, which takes linear time in the worst case.

Version Control System. GIT

A Version Control System (VCS) is a tool that helps you manage changes to files over time. It’s especially useful in coding and collaborative projects. 

The main goals of a Version Control System (VCS) are:

Backup and Restore: Think of VCS as a “save game” for your project. You can save different versions as you go and go back to any previous one if something breaks.

Synchronization:When working with others, VCS keeps everyone’s work up to date, so everyone has the latest version of the project.

Undo:If you make a mistake, VCS lets you undo changes or return to an earlier version of your work.

Track Changes:VCS keeps a record of every change, who made it, and when. It’s like a project diary that helps you understand how things evolved.

Sandboxing:You can try out new ideas without affecting the main project. This “safe zone” lets you test things freely.

Branching:You can create separate “paths” to work on different features or fixes. Each path is separate but can be merged back into the main project later.

Lock-Modify-Unlock and Copy-Modify-Merge are two approaches for managing file changes in Version Control Systems (VCS).

Git is a popular version control system that helps developers track and manage changes to their code. Originally created by Linus Torvalds in 2005 for Linux kernel development, Git has become widely used across software projects due to its speed, efficiency, and support for distributed, collaborative workflows.

git add: Moves changes to the Staging Area.

git commit: Commits changes from the Staging Area to the Local Repository.

git commit -am "Your commit message here": Stages and commits tracked changes only; ignores new untracked files.

git push: Sends local commits to the Remote Repository.

git fetch: Retrieves changes from the Remote Repository without merging.

git pull: Retrieves and merges changes from the Remote Repository.

git checkout: Switches branches or restore files to a previous state in the working area.

git clone: Copies a Remote Repository to your local machine.

git log: Displays commit history.

git restore <file>:Removes your changes and resets to the last commit. 

git restore --staged <file>: Unstages the file without discarding your changes.

git clean: remove untracked files from your working directory.

git reset <file_name>: Unstages file, keeps changes in working directory.

git reset --soft HEAD^: Undo commit from local repository, keep changes in staging area.

git reset --mixed HEAD^: Undo commit from local repository, keep changes in working directory.

git reset --hard HEAD^: Reset current branch to specific commit, discarding all changes in staging and working directory.

git revert HEAD: Revert the last commit from remote repository by creating a new commit.

git branch: Display all local branches available.

git checkout -b <branch-name>: Create and switch to branch.

git checkout <branch-name>: Switch to branch.

git switch main git merge feature_branch: Switch to the target branch and merge changes from feature-branch into main.

git branch -D <branch-name>: Force deletes branch, even if unmerged.

git branch -d <branch-name>: Safely deletes branch if fully merged.

git remote -v: Lists all Git remotes with their fetch and push URLs displayed.

git remote remove origin: Removes the "origin" remote link, disconnecting from the remote repository.

git stash save --include-untracked "message": Temporarily saves your uncommitted changes, including untracked files, allowing you to switch branches or pull updates without losing your work.

git stash apply stash@{0}: Applies the most recent stash to your working directory.

git stash list: Shows a list of all stashed changes.

git stash drop: Deletes a specific stash.

git stash pop: Applies the most recent stash and deletes it from the stash list.

git merge main: Integrates changes from one branch into another, creating a merge commit.

git cherry-pick <commit-hash>: Applies specific commits from one branch onto another, selectively including changes. Switch to the target branch (the branch where you want to apply the commit).

git rebase main: Integrates changes from main into feature-branch while keeping a linear, clean.

Stream in Java

    Java Streams is a powerful feature introduced in Java 8 that simplifies the processing of collections and sequences of data. Streams enable you to perform complex operations on data with concise and expressive code.

Stream is a sequence of data that you can process in a declarative and functional style. It allows you to perform operations such as filtering, mapping, and reducing on a collection of data. Streams can be used with various data sources, including arrays, collections, and even I/O channels.

- Arrays: You can create a stream from an array using the Arrays.stream() method.

List<String> names = Arrays.asList("Alice", "Bob", "Charlie");

Stream<String> nameStream = names.stream();

- Collections: Java collections such as lists, sets, and maps can be converted to streams using the stream() method.

List<String> names = Arrays.asList("Alice", "Bob", "Charlie");

Stream<String> nameStream = names.stream();

- I/O Channels: Java provides classes like BufferedReader for reading from input sources like files. These classes can be wrapped into streams using methods like lines().

try (Stream<String> lines = Files.lines(Paths.get("file.txt"))) {

// Process the lines in the file

} catch (IOException e) {

e.printStackTrace();

}

- Stream.of() is a static factory method in Java's Stream class that allows you to create a stream from a sequence of elements.

Stream<Integer> numbers = Stream.of(1, 2, 3, 4, 5);

Once you have a Stream, you can perform various operations on it. Stream operations can be categorized into two types: intermediate and terminal operations.

Intermediate operations transform the elements of the stream and produce a new stream as a result. Some common intermediate operations in Java streams include filter, map, flatMap, distinct, sorted, limit, and skip, among others.

import java.util.Arrays;

import java.util.List;

import java.util.stream.Collectors;

public class Main {

public static void main(String[] args) {

List<String> words = Arrays.asList("apple", "banana", "orange", "grape", "banana");

// Filter words starting with 'a'

List<String> filteredWords = words.stream()

.filter(word -> word.startsWith("a"))

.collect(Collectors.toList());

System.out.println("Words starting with 'a': " + filteredWords);

// Map each word to its length

List<Integer> wordLengths = words.stream()

.map(String::length)

.collect(Collectors.toList());

System.out.println("Word lengths: " + wordLengths);

// Remove duplicates

List<String> distinctWords = words.stream()

.distinct()

.collect(Collectors.toList());

System.out.println("Distinct words: " + distinctWords);

// Sort words alphabetically

List<String> sortedWords = words.stream()

.sorted()

.collect(Collectors.toList());

System.out.println("Sorted words: " + sortedWords);

// Limit to first 3 words

List<String> firstThreeWords = words.stream()

.limit(3)

.collect(Collectors.toList());

System.out.println("First three words: " + firstThreeWords);

// Skip first 2 words

List<String> skippedFirstTwoWords = words.stream()

.skip(2)

.collect(Collectors.toList());

System.out.println("Skipped first two words: " + skippedFirstTwoWords);

}

}

Words starting with 'a': [apple]

Word lengths: [5, 6, 6, 5, 6]

Distinct words: [apple, banana, orange, grape]

Sorted words: [apple, banana, banana, grape, orange]

First three words: [apple, banana, orange]

Skipped first two words: [orange, grape, banana]

Terminal operations in Java streams are the final operations that produce a result or a side-effect. Once a terminal operation is applied to a stream, it consumes the stream and produces a result, such as a list, a value, or even performing an action like printing elements.

import java.util.Arrays;

import java.util.List;

import java.util.Optional;

import java.util.stream.Collectors;

public class Main {

public static void main(String[] args) {

List<String> words = Arrays.asList("apple", "banana", "orange", "grape", "banana");

// forEach terminal operation

System.out.println("Printing each word:");

words.stream().forEach(System.out::println);

// count terminal operation

long wordCount = words.stream().count();

System.out.println("Total words count: " + wordCount);

// min/max terminal operation

Optional<String> minWord = words.stream().min(String::compareToIgnoreCase);

minWord.ifPresent(min -> System.out.println("Minimum word: " + min));

// findFirst terminal operation

Optional<String> firstWord = words.stream().findFirst();

firstWord.ifPresent(first -> System.out.println("First word: " + first));

// anyMatch terminal operation

boolean hasApple = words.stream().anyMatch(word -> word.equals("apple"));

System.out.println("Does the list contain 'apple'? " + hasApple);

// allMatch terminal operation

boolean allHaveLengthGreaterThanTwo = words.stream().allMatch(word -> word.length() > 2);

System.out.println("Do all words have length greater than 2? " + allHaveLengthGreaterThanTwo);

// noneMatch terminal operation

boolean noneHaveLengthGreaterThanTen = words.stream().noneMatch(word -> word.length() > 10);

System.out.println("Do none of the words have length greater than 10? " + noneHaveLengthGreaterThanTen);

// collect terminal operation toList

List<String> collectedList = words.stream().filter(word -> word.length() > 5).collect(Collectors.toList());

System.out.println("Words with length greater than 5: " + collectedList);

// reduce terminal operation

Optional<String> concatenatedWords = words.stream().reduce((word1, word2) -> word1 + ", " + word2);

concatenatedWords.ifPresent(concatenated -> System.out.println("Concatenated words: " + concatenated));

// toArray terminal operation

Object[] wordsArray = words.stream().toArray();

System.out.println("Words as array: " + Arrays.toString(wordsArray));

}

}

Printing each word:

apple

banana

orange

grape

banana

Total words count: 5

Minimum word: apple

First word: apple

Does the list contain 'apple'? true

Do all words have length greater than 2? true

Do none of the words have length greater than 10? true

Words with length greater than 5: [orange, banana]

Concatenated words: apple, banana, orange, grape, banana

Words as array: [apple, banana, orange, grape, banana]

Lambda Expressions in Java

    Lambda expression is a new and important feature of Java which was included in Java SE 8. It provides a clear and concise way to represent one method interface using an expression. It is very useful in collection library. It helps to iterate, filter and extract data from collection.

The Lambda expression is used to provide the implementation of an interface which has functional interface. It saves a lot of code. In case of lambda expression, we don't need to define the method again for providing the implementation. Here, we just write the implementation code.

(argument-list) -> {body}  

Java lambda expression is consisted of three components.

1) Argument-list: It can be empty or non-empty as well.

2) Arrow-token: It is used to link arguments-list and body of expression.

3) Body: It contains expressions and statements for lambda expression.

Without Lambda Expression

interface Drawable{

public void draw();

}

public class LambdaExpressionExample {

public static void main(String[] args) {

int width=10;

//without lambda, Drawable implementation using anonymous class

Drawable d=new Drawable(){

public void draw(){System.out.println("Drawing "+width);}

};

d.draw();

}

}

Lambda Expression Example

@FunctionalInterface //It is optional

interface Drawable{

public void draw();

}

public class LambdaExpressionExample2 {

public static void main(String[] args) {

int width=10;

//with lambda

Drawable d2=()->{

System.out.println("Drawing "+width);

};

d2.draw();

}

}

If there is only one statement, you may or may not use return keyword. You must use return keyword when lambda expression contains multiple statements.

interface Addable{

int add(int a,int b);

}

public class LambdaExpressionExample6 {

public static void main(String[] args) {

// Lambda expression without return keyword.

Addable ad1=(a,b)->(a+b);

System.out.println(ad1.add(10,20));

// Lambda expression with return keyword.

Addable ad2=(int a,int b)->{

return (a+b);

};

System.out.println(ad2.add(100,200));

}

}

Functional Interfaces in Java

    An Interface that contains exactly one abstract method is known as functional interface. It can have any number of default, static methods but can contain only one abstract method. It can also declare methods of object class.

@FunctionalInterface

interface sayable{

void say(String msg); // abstract method

// It can contain any number of Object class methods.

int hashCode();

String toString();

boolean equals(Object obj);

}

public class FunctionalInterfaceExample2 implements sayable{

public void say(String msg){

System.out.println(msg);

}

public static void main(String[] args) {

FunctionalInterfaceExample2 fie = new FunctionalInterfaceExample2();

fie.say("Hello there");

}

}

Java provides predefined functional interfaces to deal with functional programming by using lambda and method references.

Interface	Description
BiConsumer<T,U>	It represents an operation that accepts two input arguments and returns no result.
Consumer<T>	It represents an operation that accepts a single argument and returns no result.
Function<T,R>	It represents a function that accepts one argument and returns a result.
Predicate<T>	It represents a predicate (boolean-valued function) of one argument.
BiFunction<T,U,R>	It represents a function that accepts two arguments and returns a a result.
BinaryOperator<T>	It represents an operation upon two operands of the same data type. It returns a result of the same type as the operands.
BiPredicate<T,U>	It represents a predicate (boolean-valued function) of two arguments.
BooleanSupplier	It represents a supplier of boolean-valued results.
DoubleBinaryOperator	It represents an operation upon two double type operands and returns a double type value.
DoubleConsumer	It represents an operation that accepts a single double type argument and returns no result.
DoubleFunction<R>	It represents a function that accepts a double type argument and produces a result.
DoublePredicate	It represents a predicate (boolean-valued function) of one double type argument.
DoubleSupplier	It represents a supplier of double type results.
DoubleToIntFunction	It represents a function that accepts a double type argument and produces an int type result.
DoubleToLongFunction	It represents a function that accepts a double type argument and produces a long type result.
DoubleUnaryOperator	It represents an operation on a single double type operand that produces a double type result.
IntBinaryOperator	It represents an operation upon two int type operands and returns an int type result.
IntConsumer	It represents an operation that accepts a single integer argument and returns no result.
IntFunction<R>	It represents a function that accepts an integer argument and returns a result.
IntPredicate	It represents a predicate (boolean-valued function) of one integer argument.
IntSupplier	It represents a supplier of integer type.
IntToDoubleFunction	It represents a function that accepts an integer argument and returns a double.
IntToLongFunction	It represents a function that accepts an integer argument and returns a long.
IntUnaryOperator	It represents an operation on a single integer operand that produces an integer result.
LongBinaryOperator	It represents an operation upon two long type operands and returns a long type result.
LongConsumer	It represents an operation that accepts a single long type argument and returns no result.
LongFunction<R>	It represents a function that accepts a long type argument and returns a result.
LongPredicate	It represents a predicate (boolean-valued function) of one long type argument.
LongSupplier	It represents a supplier of long type results.
LongToDoubleFunction	It represents a function that accepts a long type argument and returns a result of double type.
LongToIntFunction	It represents a function that accepts a long type argument and returns an integer result.
LongUnaryOperator	It represents an operation on a single long type operand that returns a long type result.
ObjDoubleConsumer<T>	It represents an operation that accepts an object and a double argument, and returns no result.
ObjIntConsumer<T>	It represents an operation that accepts an object and an integer argument. It does not return result.
ObjLongConsumer<T>	It represents an operation that accepts an object and a long argument, it returns no result.
Supplier<T>	It represents a supplier of results.
ToDoubleBiFunction<T,U>	It represents a function that accepts two arguments and produces a double type result.
ToDoubleFunction<T>	It represents a function that returns a double type result.
ToIntBiFunction<T,U>	It represents a function that accepts two arguments and returns an integer.
ToIntFunction<T>	It represents a function that returns an integer.
ToLongBiFunction<T,U>	It represents a function that accepts two arguments and returns a result of long type.
ToLongFunction<T>	It represents a function that returns a result of long type.
UnaryOperator<T>	It represents an operation on a single operand that returnsa a result of the same type as its operand.