CMSC 132A Lecture 33: Linked Lists
CMSC132A Lecture 33: Linked Lists
Another data structure worth talking about is the Linked List. A linked list is a linear data
structure, just like an array. Unlike an array though, the size of a linked list is not fixed.
That means we don’t have to predetermine the size at creation. Inserting an element
into an array is also difficult because we have to insert at the end and that involves
shifting everything that came before it down one space. Not so with the linked list.
Linked Lists
How do you represent a linked list? Well you point to the start of the linked list. This is
called the Head of the list. If the list is empty, the head happens to point to null.
Otherwise the head points to the first element of the list.
Class linkedListExample{
Node head;
Class nodeExample{
String name;
Node next;
Node(String name){
this.name=name;
next=null;
}
}
}
Document Summary
Another data structure worth talking about is the linked list. A linked list is a linear data structure, just like an array. Unlike an array though, the size of a linked list is not fixed. That means we don"t have to predetermine the size at creation. Inserting an element into an array is also difficult because we have to insert at the end and that involves shifting everything that came before it down one space. Well you point to the start of the linked list. This is called the head of the list. If the list is empty, the head happens to point to null. Otherwise the head points to the first element of the list. Note that we didn"t really have to put that the next node was null. This is because all objects have a default value of null. We can use that to link the nodes together! llist. head. next=second; second. next=third; third. next=fourth; fourth. next=fifth;