Lectures 7/8 – Linked Lists

Lecture 7:

0:20 Hi everyone ! today I’m gonna talk about lists (first part :), I would add)

How can a list be stored….?

Into an array, obviously ! .. but this can trigger some disadvantages:

  1. array have a fix length (I think this triggers almost all other disadvantages)
  2. cannot properly insert an element at the beginning or into the middle of a list (the explanation you have it at 4:10)
  3. what if your array is not sufficient enough? … have to allocate new one

5:50 how to get rid of those issues? use linked lists

6:40 its elements are called nodes

6:49 each node stores two things: an item and a reference to the next node in the list

public class ListNode{
int item;        // the item
ListNode next;   // the reference
}

ListNode l1 = new ListNode;
ListNode l2 = new ListNode;
ListNode l3 = new ListNode;
l1.item = 7;
l2.item = 0;
l3.item = 6;
l1.next = l2;
l2.next = l3;
l3.next = null;

12:50 in Java null has to be lowercase

how can someone to use a reference to its own class type? well… tough question and I thought of dedicating a separate post. I only remember that I just wrote this valuable sentence:

pointers (including here pointers to objects) have a constant length on a machine, this is why self-referential classes can be created

13:43 in Java you can have references only to objects not to variables, that’s why you cannot make l1.next point to l2, but directly to the ListNode object that l2 also references

15:03 a constructor for the ListNode class

public ListNode (int item, ListNode next)
{
this.item = item;
this.next = next;
}

let’s throw a short constructor too:

public ListNode (int item){
this (item, null);  // calls previous constructor
}

18:42 advantages of linked lists:

  1. inserting an item takes a constant amount of time (not one proportional to the array’s length)
  2. don’t have to worry about how long the list is

21:25 a method for inserting an item:

public void insertAfter (int item){

next = new ListNode (item, next);

}

25:04 interesting to hear the explanations after executing this insertAfter function (important to the distinguish between the next l-value and the next taken as parameter of ListNode constructor)

33:00 Disadvantages:

  1. finding the n’th item of a linked list takes time proportional to the length of the list (in case of arrays this can be done in constant time)

36:00 Let’s write some code that finds the last element of the list

public ListNode nth (int position){
if (position == 1){
return this;
} else if ((position < 1) || (next == null) ){
return null;}
else {
return next.nth(position -1); }
}

41:50 lists of objects, there are basically two types: single linked lists and double linked lists

if you want your list to refer to objects, not only to integers (and remember that in Java strings of characters are objects, so you may need to declare a list of strings), you’ll have to declare your item of type Object

public class SListNode{
public Object item;
public SListNode next;
}

43:55 a separate ListClass is created. Why? Because of some un-synchronizing issues that may arise when two different references point to the same List, and also because of impossibility of declaring an empty list.
the separate SList class that maintains the header of the list (the first element of the list).

This class has to contain two elements: header, which will be of SListNode type and size element.

Lecture 8

private and public keywords … why would we need them?
basically to enforce the encapsulation principle, which is, along polymorphism and inheritance (some would add also generic programming), one of the key principles of object oriented programming.

1:25 one thing which is strongly related to what I’ve written above is that private keyword makes your program not to depend on private variables, so if you want to change the implementation of your class, you only have to change those specific private members and nothing else

7:14 some software engineering definitions: Interfaces, Abstract Data types (ADT), Invariants

15:32 another advantage of having a SList ADT class: you can enforce invariants.
Fields of SList are private (which is a very important thing, since no one except the designer of the class can “tamper” the class implementation). No method of SList class returns a SListNode object

22:20 Doubly linked lists: solves the issue of inserting and deleting and item at the end and in the middle of the list (has a constant time for doing this, you do not have to step through each element of the list). The problem with single linked lists was that you can refer only forward to list elements, there is no way of going backward.

Jonathan says about a workaround to solve the problem of inserting at the end of the list, with a tail pointer, but it is still difficult to delete items at the end of the list, since tail pointer.cannot backup

public class DListNode{
Object item;
DListNode next;
DListNode prev
}

public class DList{
private DListNode head;
private DListNode tail;
}

33:23 after the example with the deletion of the last item in the list (if the list has more than two elements) the “removed” node will get garbage collected, since there is no reference that points to it.

Important to know when an object gets garbage collected: when no reference points to it.

34:10 simplify and also make more elegant the DList implementation: sentinel node which will not make part of the list data structure (the users of the class implementing the list won’t be aware of its presence) and also there will be pointers inside the list nodes (prev and next) which will be null and the list will be circular.

Advertisements

One Response to Lectures 7/8 – Linked Lists

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: