24. Linked List: Basics-1

Basics-

# Intro to Linked List-

1. Here, elements are not in contigous locations.
2. Size of a linked list can be changed at any moment.
3. example of linked list is a browser's forward and backward button.
-------
4. It consists of head, which is 1st node & entry point to a Linked List.
5. Each element stores 2 things- a value & a pointer to the next elmt
-------
6. Elements of a 1D LL only have a next ptr, while 2D LL have both next & prvs ptr...   
-----------------------------------------------------------------------------------------------------------------------------

# Pointers-

in 32-bit system,  pointer takes 4 bytes
in 64-bit system,  pointer takes 8 bytes
-----------------------------------------------------------------------------------------------------------------------------
# Struct-

a self defined data type...
It needs a constructor to initialise things.
if we use class keyword instead of struct we can use oops concepts as well

We will prefer using dynamic allocation-
-----------------------------------------------------------------------------------------------------------------------------
# Constructors

- they are special functions
- used to initialise objects of the classes
- we can have multiple constructors
-----------------------------------------------------------------------------------------------------------------------------
1. Converting array to LL- 
time: O(n)
------------
for every element-
1. create new node pointing to null
2. point prev node to curr node
3. set prev node pointer to curr node

mover node is used to move &
temp node is used to create & store new nodes
---------------------------------------------------------------------------------------------------------------------------
2. Traversal-

-------------------------------------------------------------------------------------------------------------
3. Length of linked list-

traversal mein ek counter lagado cout se pehle
-------------------------------------------------------------------------------------------------------------
4. Searching for a target node-
time: O(n)
-------------------------------------------------------------------------------------------------------------

Comments

Post a Comment

Popular posts from this blog

30.) DP on subsequences

Image
Subset sum = target✅⭐ Partition equal subset sum✅ Partition array into 2 subsets with min abs [sum(v1)-sum(v2) ]✅ Count subsets with sum k✅⭐ Count partitions with given diff✅ target sum✅ 0/1 knapsack✅⭐ min coins✅---->count min coins to be taken coin change-2--->count n(ways) of taking coins⭐✅ unbounded knapsack✅ rod cutting problem✅ ----------------------------------------------------------------------------------------------------------------------------- 2 ways to generate all subsequences- Power Set, or Recursion subset means subsequence in dsa ----------------------------------------------------------------------------------------------------------------------------- 1. Target Sum- QUES- return true if there exists a subset with sum equal to the target in the array... Soln assuming all array elements are positive  here f(n-1,target) will tell if there's a subsequence till n-1 index with sum = target 1.) RECURSIVE SOLN-        ( time: 2^n    ...
Read more

36. Graphs-2 (traversal problems)

Image
1. No. of provinces Count total components in a graph, using any traversal technique ----------------------------------------------------------------------------------------------------------------------------- 2. Rotten oranges⭐     Multi source BFS time: O(n*m)   space: O(n*m) -------------- - count all fresh at start and then count if these many will rot in the process or not - here we do not need a visited matrix since we can modify given - we update time each time there rots atleast one orange in a BFS cycle --------------------------------------------------------------------------------------------------------------------------- 3. No. of Islands Count no. of islands (land surrounded by water in 4 directions) ---------------------------------------------------- time: O(n^2)  space: O(n^2) No. of islands = no. of graph components ----------------------------------------------------------------------------------------------------------------------------- 4. ...
Read more

35. Graphs-1 (basics)

Image
# Note -  1. it has nodes/vertices (N) connected by edges (E) 2. d egree(N)  = n(edges) connected to a node 3. in-degree(N) = no. of in-going edges  4. out-degree(N) = no. of out-going edges  5.  Total degree of undirected graph = (2*E) 6.  DAG - directed acyclic graph 7.  Path -  a sequence of nodes where all  adj nodes have a direct edge b/w them -------------------------------------------------------------------------------------------------------------------------- 1. Representation- 1. Adjacency Matrix:  space: O(n^2) store info about presence of edges between 2 nodes -------------------------------------------------------- 2. Adjacency list:   space: O(n) - store info about adjacent neighbours of a node - for unweighted graph instead of a pair we will store them as integer array ----------------------------------------------------------------------------------------------------------------------------- 2. BFS- time: O(N+...
Read more