Is DoubleLinkedList method inefficient?

EasternPremiseByEasternPremise

I wrote a method myself to add it to the back

 public void addBack(int data){        Node n = new Node(data);        if(rear == null){            rear = n;            front = n;            return;        }               if( front.next == null){            front.next = n;            n.before = front;            rear = n;        }        n.before = rear;        rear = n;        rear.before.next = rear;           }

And this is the pattern function. What are the disadvantages of mine? Or where are there errors? I've tested it, and everything seems to work when inserted once, or even when inserted multiple times.

 public void addAtEnd(int dataValue){        if (front == null){            addFront(dataValue);            return;        }        Node lastNode = front;        while (lastNode != null){            if (lastNode.next == null){                Node newNode = new Node(dataValue);                newNode.next = null;                newNode.before = lastNode;                lastNode.next = newNode;                lastNode.next = newNode;                rear = newNode;                return;            }            lastNode = lastNode.next;        }    }
(1 votes)
Loading...

Similar Posts

Learn Java?

Bykabik334

I'd like to learn Java. So far, I've programmed a bit in Python and C, but to be honest, I should have done a better job at the beginning. That's why I want to do it right this time. Do you have any tips on how I can best learn Java? I'm currently trying W3schools.

Subscribe
Notify of
4 Answers
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
KarlRanseierIII
KarlRanseierIII
1 year ago

The second variant looks like a typical implementation for Single Linked without Tailpointer.

Because then you have to iterate about the list.

2
EasternPremise
Author
EasternPremise
1 year ago
Reply to  KarlRanseierIII

So my own is better?

0
slayer791
slayer791
1 year ago

However, there are some potential problems and inefficient aspects in your implementation:

  1. Unnecessary review of the empty list: In your
  2. addBack
  3. -Method check if
  4. rear == null
  5. to determine whether the list is empty. If this is the case, add the element and return. Otherwise proceed with adding the item. This additional review is not necessary because you already have the same review in your
  6. addAtEnd
  7. -Method in
  8. addFront
  9. to carry out. So you could just
  10. addFront
  11. call if
  12. front == null
  13. is to be carried out instead of an additional review.
  14. Dopting the line
  15. lastNode.next = newNode;
  16. : In your
  17. addAtEnd
  18. -Method show twice
  19. lastNode.next
  20. the value
  21. newNode
  22. too. The second assignment is superfluous and can be removed.
  23. Poor runtime complexity: Your current implementation has a runtime complexity of O(n), as you need to run a loop every time to find the last item in the list before adding the new item. This can be inefficient, especially if the list contains many elements. A more efficient method of adding at the end of the list would be to keep a pointer on the last item of the list and to attach the new item directly to it. This would reduce the runtime complexity to O(1).

Here is a revised approach that addresses the problems mentioned and provides a more efficient implementation:

java

Copy code
public void addBack(int data) { Node newNode = new Node(data); if (front == null) { front = newNode; rear = newNode; } else { newNode.before = rear; rear.next = newNode; rear = newNode; } }

In this revised version will be

rear

used as a pointer to the last item of the list. If the new item is added, it will be added directly to

rear

hung, thereby avoiding the loop for searching for the last element. This will make the addition at the end of the list more efficient regardless of the length of the list.

1
EasternPremise
Author
EasternPremise
1 year ago
Reply to  slayer791

So mine would be the above that with the loop is the sample solution

0