Reverse a linked list algorithm

Published by Igor Khrupin on

Basics

Linked list is a data structure each element of those has link to the next element.

Each element of the linked list called node

The node of linked list called head. To identify the whole linked list we need link to head only.

The linked lists are great in insertion and deleting first and last elements. They can used for implementing stacks, queues.

Time and complexity for LinkedList

OperationComplexity explanationComplexity formula
InsertionconstantO(1)
DeletionconstantO(1)
SearchlinearO(n)
SpacelinearO(n)

Algorithm theory

Task definition

We have a linked list.

We need reverse items in the existing linked list.

Solution

The simplest way to solve the task is to iterate through the list and set the previous node as the next node for each node. The next node for the first node must be null.

The complexity in this case will be 0(n).

Diagram

PlantUML Syntax:<br /> @startuml</p><p>start</p><p> repeat</p><p> if (“Is Head Node?”) then (yes)<br /> :Set next node as NULL;<br /> else (no)<br /> :Set next node as previous;<br /> endif<br /> :Save current node in previous field;</p><p> repeat while (Next node is NULL) is (no)</p><p> :Save the previous field as head;</p><p>stop</p><p>@enduml<br />

Sample code

Below you will get a link to GitHub repo with Kotlin, Java, and Python source code

Download it from github

0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.