1.
Introduction
2.
Example
2.1.
Input
2.2.
Output
3.
Algorithm
3.1.
Example Code
3.2.
Output
4.
Complexities
4.1.
Time complexity
4.2.
Space complexity
5.
5.1.
What is the definition of linked lists?
5.2.
What are the drawbacks of using a linked list?
5.3.
Why are linked lists better than arrays in terms of performance?
5.4.
To create a simple linked list, how many pointers are required?
5.5.
Is it possible to store various data types in a linked list?
6.
Conclusion
Last Updated: Mar 27, 2024

# Given a Linked List of Line Segments, Remove middle points

Manan Singhal
0 upvote

## Introduction

A linked set of coordinates is given, with adjacent points forming vertical or horizontal lines. Remove points in the middle of a horizontal or vertical line from the linked list.

## Example

### Input

``(2,3)->(4,3)->(8,3)->(10,3)->(12,3)``

### Output

``````The linked list should be changed to the following:
(2,3)->(12,3)``````

There is only one vertical line, so remove all middle points.

## Algorithm

1. With the first and second nodes of the list, respectively, initialize two pointers prev and curr.
2. Continue iterating through the list until curr is not NULL.
3. If curr's and prev's x-coordinates are equivalent (i.e., vertical line), then:
Create a start variable with the value prior, which will be used to indicate the beginning of the section.
Advance prev and curr by one node
Run a while loop until curr is not NULL and curr and prev's x-coordinates are equivalent.
Attach curr after the start and delete the prev node inside the loop.
In addition, change prev to curr and advance curr by one node.
4. If curr's and prev's y-coordinates are equal (i.e., horizontal line), then:
Create a start variable initialized to prev, which will represent the segment's start.
Advance prev and curr by one node.
Run a while loop until curr is not NULL and curr and prev's y-coordinates are equivalent.
Attach curr after the start and delete the prev node inside the loop.
In addition, change prev to curr and advance curr by one node.
5. If the two coordinates are not equal, advance prev and curr by one node.

### Example Code

``````/* C++ program to remove middle points from the linked list that represents any line segments */
#include <bits/stdc++.h>

using namespace std;

/* Creating a node with 3 fields including x, y coordinates and a pointer representing next node */
class Node {
public:
int x, y;
Node *next;
};

/* Insert a node at the beginning using this function */
void push(Node ** head_ref, int x,int y)
{
Node* new_node =new Node();
new_node->x = x;
new_node->y = y;
}

/* Function to print a linked list */
{
while (temp != NULL)
{
cout << "(" << temp->x << "," << temp->y << ")-> ";
temp = temp->next;
}
cout<<endl;

}

/* Function to remove Next from the linked list and link nodes accordingly */
{
Next->next = NULL;
free(Next);
}

/* Function deletes middle nodes in a sequence of any line segments represented by a linked list. */
{
/* If only one node or no node then return back */

Node *NextNext = Next->next ;

/* Check if this is a horizontal line or vertical line */
{
/* Find middle nodes with same x value, and delete them */
while (NextNext != NULL && Next->x == NextNext->x)
{

/* Update Next and NextNext for next iteration accordingly */
Next = NextNext;
NextNext = NextNext->next;
}
}
{
/* Find middle nodes with same y value, and delete them */
while (NextNext != NULL && Next->y == NextNext->y)
{
Next = NextNext;
NextNext = NextNext->next;
}
}
else
{
puts("Given linked list is not valid");
return NULL;
}

/* Recursion for next segment */

}

/* Main Code */
int main()
{

cout << "Given Linked List: \n";

{
cout << "Modified Linked List: \n";
}
return 0;
}``````

### Output

``````Given Linked List:
(0,10)-> (1,10)-> (3,10)-> (10,10)-> (10,8)-> (10,5)-> (20,5)-> (40,5)->
(0,10)-> (10,10)-> (10,5)-> (40,5)->``````

## Complexities

### Time complexity

O(n), where n represents nodes in a linked list
Reason: One nested loop is required while traversing the linked list so that the time complexity will be O(n).

### Space complexity

O(1),
Reason: No extra space required.

#### What is the definition of linked lists?

It is a data structure for storing a set of things. Linked lists can be used to store many objects of the same kind. Each node has its data as well as the following node's address. It resembles a chain.

#### What are the drawbacks of using a linked list?

Each node of the linked list points to a pointer, it requires more memory to store the elements than an array. Traversing the nodes of a linked list is quite tough. We won't be able to access any node at random in this case.

#### Why are linked lists better than arrays in terms of performance?

Arrays allow for random access and use less memory per element, but they are inefficient for insertion/deletion operations and memory allocation. Linked lists are dynamic and have lower insertion/deletion time complexity.

#### To create a simple linked list, how many pointers are required?

Three types of pointers are often required: A 'head' pointer is used to indicate the beginning of an entry in a list. A 'tail' pointer indicates the last node in a chain. The fact that the last node's following pointer goes to nothing is crucial (NULL).

#### Is it possible to store various data types in a linked list?

Yes, as long as the list is declared as a List<Object> or List<Serializable>, both string and integer extend.