like all data structures linked lists have their strengths and weaknesses. basic strengths includes; simplicity, speed of insertion and deletion, and they're quite fast when it comes to linear processing. but the main weakness is that they use more memory than arrays, and they're not good with the most sort algorithms but insertion sort and bubble sort are fine. as i said above they're good for sequential processing which means you wouldn't want to implement a binary search for a linked list, and you can't go backwards unless you're implementing doubly linked list. if you're writing a doubly linked list, it means you need more memory since you need two pointers. of course there's a hack way around it but i'm talking about the ordinary way :) i'll talk about how to deal with doubly linked lists with one pointer in another post to reduce memory usage.
basic thing is to define a node which will be the body of the list.
class Node {
int data;
Node next, prev;
}in the constructor we don't need to set the next variable to null but it's good to write it. it doesn't matter for java(it does it for you on compile time), but if you're going to implement it in c++ one day, you'll need to.
by the way, i'm implementing linked list as described in introduction to algorithms, second edition(p. 204) which means in the end we'll have unsorted doubly linked list. there's no point for implementing a singly linked list 'cos all you have to do is to omit prev pointer.
here's the insert method
public void insert(Node newData) {
newData.next = head;
if(head != null)
head.prev = newData;
head = newData;
newData.prev = null;
}
running time for insert method is o(1).when it comes to searching, linear search is the best way. as you can easily guess running time for search method is o(n), it may need to search the entire list.
public Node search(int key) {
Node cur = head;
while(cur != null && cur.data != key)
cur = cur.next;
return cur;
}
or a boolean method(which is more preferred);public boolean search(int key) {
Node cur = head;
boolean found = false;
while(cur != null) {
if(cur.data == key) {
found = true;
break;
}
cur = cur.next;
}
return found;
}now we can move onto other method which is deleting from a linked list. delete method runs in o(1) time, but if we want to delete a specific item, first we need to search for it which will end in o(n) time.
public void delete(Node a) {
if(a.prev != null) {
a.prev.next = a.next;
} else {
head = a.next;
}
if(a.next != null)
a.next.prev = a.prev;
}
we could use sentinels to dump some of the if statements though, but anyway this is the simplest implementation of a linked list. if you need more practice do the followings :)- reverse a linked list
- insert after an item
- insert before an item
- insert into middle / tail
i wanted use some graphics to show what a linked list looks like but i'm no good at using graphical tools.