DZone
Java Zone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
  • Refcardz
  • Trend Reports
  • Webinars
  • Zones
  • |
    • Agile
    • AI
    • Big Data
    • Cloud
    • Database
    • DevOps
    • Integration
    • IoT
    • Java
    • Microservices
    • Open Source
    • Performance
    • Security
    • Web Dev
DZone > Java Zone > Constant Complexity For Reversing of a List

Constant Complexity For Reversing of a List

Peter Karussell user avatar by
Peter Karussell
·
Mar. 28, 10 · Java Zone · Interview
Like (0)
Save
Tweet
7.05K Views

Join the DZone community and get the full member experience.

Join For Free

I am reading this question on stack overflow and it was irritating for me that the most people say: reversing a linked list is possible only in O(n). Okay, this is true for a single linked lists, but not for double linked lists like I will show you with my quick and dirty CarouselList:

The key point is the incrementer/decrementer:

static class Incrementer<T> {

Node<T> getNext(Node<T> node) {
return node.next;
}

Node<T> getStart(Node<T> head) {
return head;
}
}

static class Decrementer<T> extends Incrementer<T> {

@Override
Node<T> getNext(Node<T> node) {
return node.previous;
}

@Override
Node<T> getStart(Node<T> head) {
return head.next;
}
}

This way the ‘iteration order’ can be easily switched in O(1). Of course this comes to the cost of a bit more expensive iteration but this is another issue …

If the implementation could use an ArrayList (not a linked list) it would be more simple: return different iterators based on a ‘reverse’ attribute. Then either return an iterator with counter++ or return one with counter– if reverse == true

From http://karussell.wordpress.com/2010/03/27/constant-complexity-for-reversing-of-a-list/

 

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Your Old Laptop Is Your New Database Server
  • Choosing Between GraphQL Vs REST
  • Synchronization Methods for Many-To-Many Associations
  • How to Determine if Microservices Architecture Is Right for Your Business

Comments

Java Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • MVB Program
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends:

DZone.com is powered by 

AnswerHub logo