reifi reifi - 1 month ago 9
Java Question

How to determine the direction of a Linked List

I have to make a linked list that adds to itself to the left so im thinking it's something like this where the boxes are nodes and the arrow is the link:

tail [] <- [] <- [] <- ... [] head


But how do you determine the direction of the linked list when you are adding the second node?
How do you know which side it's going to be placed on?

2nd? 1st 2nd?
[] [] []


For example this code: head = new IntNode(5,head)

would add to the right if the linked list is like this:

head tail
[] -> [] -> [] -> []


But that's only when adding to an already made list with that format, so which side will it start from when creating a new linked list?

Answer

Well there is no left and right with linked lists.

That direction is just used for convenient graphical representation since we can easily picture it. You can technically draw a linked list side ways, up to down, down to up, left to right, doesn't really matter.

All linked lists have is a single direction from head to tail. Or in case of doubly linked lists, a bi-direction from head to tail and from tail to head.

I guess you could technically make a doubly linked list where all "left" or "prev" pointers are null to make it seem like it goes right. Or make all of its "right" or "next" pointers null and make it seem like it goes left. In either case, such direction has no actual meaning.

"left" and "right" are just conventions decided for easier graphical presentation of a linked list.

In memory, linked list node's value of Node.next just contains a memory address of the next node. That memory location doesn't have to physically be right next to the node. Technically, linked list pointers can zig-zag all over memory, connecting blocks wherever the OS and underlying system decided to allocate memory for them. There is no "natural" order like we are used to in real life, just sequence of pointers from head to tail

For example, these two lists are equivalent as far as the computer is concerned. I just drew them in different directions :)

linked lists