a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.
Singly-linked-list.svg A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.
A linked list is a data structure in which objects are arranged in a linear order. While arrays maintain a linear ordering through its indices, linked lists store their ordering with a pointer field next in each object.
The simple singly-linked list consists of nodes with two fields:
- A key
- A pointer next to the next node, or to NIL if it's the tail node
Doubly linked lists add one more field: a pointer to the previous node, often named prev.
The linked-list itself often keeps track of the head node and provides various operations:
- search(key) - O(n) - which returns the found node with that key or NIL if not found
- insert(x) - O(1) - which splices node x onto the front of the list
- delete(x) - O(1) - which splices node x out of the list. Assuming the list is doubly-linked, this is usually done by re-setting the pointers of x's prev and next elements to point to each other
- delete(key) - O(n) - which runs the O(n) search(key) then the O(1) delete(x)
- Single or double - if a list is singly-linked, there is only a next pointer. If it is doubly-linked, there are both prev and next pointers.
- Sorted or unsorted - a sorted linked list maintains an ordering of node keys
- Circular - a list in which the next pointer of the list's tail element points to the head element
- Separate classes for lists and nodes (as described above) or just nodes - sometimes defining a linked list Node class is all you'll need for an interview question, so it's unnecessary to go through the trouble of defining a List class
Store a list of ints as an array
- Insert item at beginning or middle
-> time proportional to length of array
- Arrays have a fixed length
Made up of "nodes" Each node has
- an item
- a reference to next node in list
public class ListNode
{
int item;
ListNode next;
}
ListNode l1 = new ListNode(), l2 = new ListNode(),
l3 = new ListNode();
l1.item = 7;
l2.item = 0;
l3.item = 6;
l1.next = l2;
l2.next = l3;
l3.next = null;
public ListNode(int item , ListNode next)
{
this.item = item;
this.next = next;
}
public ListNode(int item)
{
this(item, null);
}
ListNode l1 = new ListNode(7, new ListNode(0, new ListNode(6)));
Advantages over array lists:
- inserting item in middle of linked list takes constant time if you have reference to previous node
- moreover, list can keep growing until memory runs out
Inserts a new item afer "this"
public void insertAfter(int item)
{
next = new ListNode(item, next);
}
l2.insertAfter(3);
- Finding the nth item of a linked list takes time proportional to n -> length of list (constant-time on array lists)
public ListNode nth(int position)
{
if (position == 1)
{
return this;
}
else if ((position < 1) || (next == null))
{
return null;
}
else
{
return next.nth(position-1);
}
}
List of Objects Reference any object by declaring a reference of type Object.
public class SListNode
{
public Object item;
public SListNode next;
}
A List Class 2 problems with SListNodes
- Insert new item at beginning of list.
x = new SListNode("soap", x);
- How do you represent an empty list x = null;
Run-time error if you call a method on a null object.
Solution: Separate SList class that maintains head of list.
public class SList
{
private SListNode head;
private int size;
public SList()
{
head = null;
size = 0;
}
public void insertFront(OBject item)
{
head = new SListNode(item, head);
size++;
}