Doubly Linked List – Add Node at Front and Rear

Let’s add the Node at Front and Rear in Doubly Linked List

 

Linked List

Linked List
A singly linked list is a data structure having a list of elements where each element has a reference pointing to the next element in the list. Its elements are generally referred to as nodes; each node has a data field containing a data value and a next field pointing to the next element in the list (or null if it is the last element in the list). The diagram below depicts a linked list of length 3:

1456952785-0261650af4-myLinkedList

The sample code below demonstrates how to create a LinkedList of Strings, and some of the operations that can be performed on it.

The above code produces the following output:

Implement a function to check if a linked list is a palindrome

To approach this problem, we can picture a palindrome like 0 -> 1 -> 2 -> 1
– > 0. We know that, since it’s a palindrome, the list must be the same backwards and
forwards.This leads us to our first solution.

Solution #1: Reverse and Compare

Our first solution is to reverse the linked list and compare the reversed list to the original
list. If they’re the same, the lists are identical.
Note that when we compare the linked list to the reversed list, we only actually need to
compare the first half of the list. If the first half of the normal list matches the first half
of the reversed list, then the second half of the normal list must match the second half
of the reversed list.

Solution #2: Iterative Approach

We want to detect linked lists where the front half of the list is the reverse of the second
half. How would we do that? By reversing the front half of the list. A stack can accomplish
this.
We need to push the first half of the elements onto a stack. We can do this in two
different ways, depending on whether or not we know the size of the linked list.
If we know the size of the linked list, we can iterate through the first half of the elements
in a standard for loop, pushing each element onto a stack. We must be careful, of course,
to handle the case where the length of the linked list is odd.
If we don’t know the size of the linked list, we can iterate through the linked list, using
the fast runner / slow runner technique described in the beginning of the chapter. At
each step in the loop, we push the data from the slow runner onto a stack. When the
fast runner hits the end of the list, the slow runner will have reached the middle of the
linked list. By this point, the stack will have all the elements from the front of the linked
list, but in reverse order.