Before I start, let me caution you that this post is not about LinkedList [Java Doc] API of Java. LinkedList API of Java is a specialized implementation of doubly linked list. This post talks in general about linked data structures (i.e. linked list) and implementation of single linked list in Java.
Definition
Linked data structures are composed of distinct chunks of memory; and these chunks are bounded/linked through pointers. These memory chunks are referred as nodes. As nodes are not stored in contiguous memory so adding or removing individual nodes is quite easier (unlike an array). But one drawback is that random access to node is not possible.
typedef struct node {In C language; *p denotes the item that is pointed to by pointer p, and &x denotes the address (i.e. pointer) of a particular variable x. A special null value is used to denote the termination of the list.
item_type item; //data stored in node
struct list *next; //points to successor
}node;
Let's cover them in detail
C pointers:
int var = 20;
int *ip; //pointer to an integer
ip = &var; //store address of var in pointer ip
Java references:
Integer x = new Integer(20); //x is reference to Integer
Usually, Java references are implemented as pointers in C; but specification doesn't say it explicitly. Java reference should be just an abstraction on C pointers (i.e. references in Java will be implemented using C pointers). I am not going to stress if both are same or not; it's debatable!
Implementation
Below is custom single linked list implementation in Java. I have just provided add and print method.
package algo; /** * Generic single linked list implementation with generics * * @author Siddheshwar */ public class SingleLinkedList<E> { Node<E> start; // points to the head or first node /** * Node class */ private class Node<E> { E data; Node<E> next; public Node(E data, Node<E> next) { this.data = data; this.next = next; } public E getData() { return data; } public Node<E> getNext() { return next; } public void setNext(Node<E> next) { this.next = next; } } public void add(E d) { // add at the end of list if (start == null) { start = new Node<E>(d, null); } else { Node<E> tmp = start; while (tmp.next != null) { tmp = tmp.next; } tmp.setNext(new Node<E>(d, null)); } } public void print() { Node<E> current = start; System.out.print(" values in link-list are :"); while (current != null) { System.out.print(current.getData() + "--> "); current = current.getNext(); } System.out.println("null"); } public static void main(String[] args) { SingleLinkedList<String> sll = new SingleLinkedList<>(); sll.add("abc"); sll.add("def"); sll.print(); } }
Output :
values in link-list are :abc--> def--> null
values in link-list are :abc--> def--> null
Complexity of common operations
- Insert/Update/delete at end of list: O(n) . Need to traverse whole list.
- Insert at the beginning/head of the list : O(1)
- Find the size of list : O(n). But it can be achieved in O(1) if you keep track of the count in a separate attribute (increment its value on each addition and decrement on each deletion).
References from Java
- LinkedList [Java Doc] : Doubly linked list implementation of the List and Deque interfaces.
- LinkedHashMap [Java Doc] : Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. Linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map.
- LinkedHashSet [Java Doc] : Hash table and linked list implementation of the Set interface, with predictable iteration order.
Related Post :Implementing Doubly linked list in Java
You may also like my tutorial - Internal life of LinkedList in java
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDeleteGreetings! Very useful advice within this article! It is the little
ReplyDeletechanges that make the largest changes. Thanks a lot for sharing!
my web-site ... Corrie Morgen
It's going to be end of mine day, but before ending I am reading this impressive paragraph to increase my knowledge.
ReplyDeleteMy webpage: After Effects Tutorial
Hello mates, nice piece of writing and good urging
ReplyDeletecommented at this place, I am truly enjoying by these.
Here is my webpage - product design and development
Thanks for ones marvelous posting! I truly enjoyed reading it, you're a great author.I will remember to bookmark your blog
ReplyDeleteand will eventually come back down the road.
I want to encourage you to continue your great work,
have a nice evening!
My blog post ... cubic zirconia