Visa källa för TDDC30 - Programmering i Java, datastrukturer och algoritmer

{| class="wikitable" style="float:right; margin-left: 30px;"
|+<b>TDDC30 </b>
|-
|colspan="2"|[[File:TDDC30 page image.png|center]]
|-
| <b> Institution </b>
| Institutionen för datavetenskap (IDA)
|-
| <b>Examinator</b> 
| [http://www.ida.liu.se/department/contact/contactcard.sv.shtml?torjo38 Torbjörn Jonsson]
|-
| <b>Kursledare</b>
| [https://www.ida.liu.se/department/contact/contactcard.sv.shtml?ernil Erik Nilsson]
|-
| <b> Examination </b>
| Laborationer (3 hp) <br> Datortentamen (3 hp)
|-
| <b> Högskolepoäng </b>
| 6 hp
|-
| <b> Undervisas för</b> 
| [[Industriell ekonomi - Linköpings universitet|Industriell ekonomi]] <br>[[Systemvetenskap - Linköpings universitet|Systemvetenskap]]
|-
| <b> Övrigt</b>
| [http://kdb-5.liu.se/liu/lith/studiehandboken/svkursplan.lasso?&k_budget_year=2016&k_kurskod=TDDC30 Kursplan] <br> [http://www4.student.liu.se/tentaresult/?kurskod=TDDC30&provkod=&datum=&kursnamn=&sort=0&search=S%F6k Tentastatistik] <br> [https://www.ida.liu.se/~TDDC30/ Kurshemsida]
|}

TDDC30 är en grundkurs i programspråket Java, datastrukturer och algoritmer. Kursen omfattar 6 högskolepoäng och undervisas både för  [[Industriell ekonomi - Linköpings universitet|Industriell ekonomi]] och för [[Systemvetenskap - Linköpings universitet|Systemvetenskap]] på [[Linköpings universitet|Linköpings universitet]]. Kursen är en påbyggnadskurs på [[TDDD11 - Programmering, grundkurs|TDDD11 - Programmering, grundkurs]] och förutsätter att studenten har grundläggande programmeringskunskaper gällande ett "programmeringstänk".

Kursen går igenom ett antal sorteringsalgoritmer, olika typer av datastrukturer, hur man skriver och använder UML-diagram, hur man använder det grafiska Swingpaketet och allmänt hur man ska tänka för att programmera objektorienterat. Examinationsmomenten innefattar 5 stycken laborationer (0-4) och en tentamen. Tentan består av en teoretisk del och en praktisk programmeringsdel.

= Java =
Java är ett av världens mest använda programmeringsspråk, just för dess operativsystemsneutralitet. I programspråket ADA som kursen TDDD11 undervisas i så använder man en kompilator som tolkar den källkod som programmeraren skrivit och gör om den till maskinkod som datorn kan köra. I Java så finns det ett mellanlager som kallas för Java Virtual Machine (JVM). JVM gör det möjlig att köra samma javakod på alla operativsystem som har stöd för detta, vilket i stort sett gör språket plattformsoberoende, det går lika bra att köra javakod i en Androidtelefon som på en Mac.

Språket är uppbyggt på klasser som på olika sätt kommunicerar och interagerar med varandra.
<br>
[https://en.wikipedia.org/wiki/Java_(programming_language) Wikipediaartikeln]

= Konstruktorer =
Varje gång man skriver en ny klass så skapas en konstruktor, skriver man ingen egen så skapas automatiskt en tom utan inparametrar. Konstruktorn skrivs ungefär som en metod i klassen där metodnamnet är namnet på klassen. Den används sedan när man initierar klassen som ett objekt. Via konstruktorn kan man skicka med data som är bra vid skapandet av objektet. Skriver man t.ex klassen Human så är det rimligt att lägga namn och ålder som inparametrar i konstruktorn, då alla människor har ett namn och en ålder. I konstruktorn kan man också skriva kod som man vill ska köras varje gång som en klass instansieras.

Här är ett exempel på hur konstruktorn skrivs:

<source lang="java">
public class Cat { // Publika klassen Cat
     
     private String name; // Instansvariabel för kattens namn
     private int age;  // Instansvariabel för kattens ålder
     
     public Cat (String name, int age) { // Detta är huvudet av konstruktorn. Vi tar in kattens namn och ålder
          this.name = name; // Vi tilldelar instansvariabeln "name" med inparametern "name"s data
          this.age = age; // Vi tilldelar instansvariabeln "age" med inparametern "age"s data
          System.Out.println("The cat's name is " + name + " and the age of the cat is " + age); // Utskrift av namn och ålder
     }
}
</source>
<br>
När man sedan instansierar ett objekt av klassen Cat skriver man på följande sätt:

<source lang="java">
Cat kattenKalle = new Cat("Kalle", 10); // Vi skickar in namnet "Kalle" och åldern 10 i konstruktorn
Cat kattenPelle = new Cat("Pelle", 2); // Vi skickar in namnet "Pelle" och åldern 2 i konstruktorn
</source>
<br>
[https://en.wikipedia.org/wiki/Constructor_(object-oriented_programming) Wikipediaartikeln]

= Objektorientering =
Objektorienterad programmering bygger på program som består av en uppsättning objekt som interagerar med varandra på olika sätt. 

== Objekt ==


<br>
[https://en.wikipedia.org/wiki/Object-oriented_programming Wikipediaartikeln] <br>

= Klass =
Java är ett objektorienterat språk som är uppbyggt på b.la klasser. En klass är ett eget kodstycke som är en mall man använder för att skapa ett objekt i Java. I klassen skriver man instruktioner om hur just den klassen/objektet fungerar. Instruktionerna (klassen) består av importering av paket, attribut och metoder. Se följande exempel:

<source lang="java">
package test; // Denna klass tillhör paketet "test"

// Detta är en kommentar. Kommentarer i Java skrivs med två stycken slash följt av en text
import java.grafisktpaket.* // Stjärnan (*) betyder att vi importerar precis alla klasser i paketet grafisktpaket
import java.util.ArrayList; // Här hämtar vi enbart klassen "ArrayList". Det är viktigt att inte hämta onödiga klasser som inte används


private int nummer; // Här skapar vi en private integer (heltalsvariabel) med namnet nummer
private double nummer2; // Här skapar vi en private double (decimalvariabel) med namn nummer2
private String namn; // Här skapar vi en private String (textsträng) med namnet namn
private boolean check; // Här skapar vi en private boolean (tvåvärdesvariabel) med namn check


public class skrivText() { // Klassen heter skrivText och är public (dvs synlig för alla).
        System.out.println("Hello World!"); // Här skrivs "Hello World!" ut i konsolen.
}
</source>

För att skapa ett objekt så instansierar man en klass, detta görs i koden man vill skapa objektet. I nedanstående exempel instansierar vi klassen <i>ArrayList</i>. Detta sker i två steg:
# Skapa en referens som ska peka på ett objekt skapat kring en specifik klass.
# Instansiera själva objektet och peka referensen på objektet.
<br>
<source lang="java">
ArrayList<String> list; // Steg 1: Här skapar referensen "list" till ett ArrayList-objekt.
list = new ArrayList<String>(); // Steg 2. Här skapas själva ArrayList-objektet som referensen "list" pekar på.
</source>

Detta kan även göras genom att skriva ihop de två stegen:
<source lang="java">
ArrayList<String> list = new ArrayList<String>();
</source>
<br>
[https://en.wikipedia.org/wiki/Class_(computer_programming) Wikipediaartikeln]

= Synlighet =
Synlighet används för att begränsa insynen och dölja implementationen av klasser, metoder och attribut. Som regel ska man visa upp så lite som möjligt, endast det som verkligen är nödvändigt. Attribut är av god sed och vana private, därför måste man komma åt dem på något annat sett. Detta gör man via getters and setters. Getter är en metod som hämtar attributet, Setter är en metod som sätter ett nytt värde på attributet.

<source lang="java>
public class testMetod() {

     private int number = 0;

     public int getNumber() { // Getter returnerar integern number
          return number;
     }

     public void setNumber(int number) { // Setter sätter number till inparameterns värde
          this.number = number;
     }
}


</source>

{| class="wikitable"
|+Olika synlighet
|-
|<b>Synlighet</b>
|Klass
|Paket
|Subklass
|Värld
|-
|public
|Ja
|Ja
|Ja
|Ja
|-
|protected
|Ja
|Ja
|Ja
|Nej
|-
|private
|Ja
|Nej
|Nej
|Nej
|}


{| class="wikitable"
|+God sed och vana
|-
|<b>Klasser</b>
|Som regel public. Används de endast internt kan mer begränsad synlighet användas
|-
|<b>Metoder</b>
|public
|-
|<b>Interna metoder</b>
|private
|-
|<b>Attribut</b>
|private (eventuellt protected om motivetat)
|}

= Statiska metoder och attribut =
Om en metod eller ett attribut hör till hela klassen i sig än en specifik instans (objekt) så ska den göras statisk. De kallas då för klassmetoder och klassvariabeler. Ett exempel på detta skulle kunna vara i ett program där man har användning för vilket år det är. Det finns ingen mening att skapa ett nytt attribut med samma år för varje objekt som instansieras. När den görs statisk så lagras attributet enbart på ett minne som tillhör klassen i sig, det vill säga oavsett hur många objekt av klassen som instansieras så skapas bara ett minnesutrymme för attributet. Detta betyder också att man kan kalla på attributet från andra klasser i samma paket utan att instansiera klassen som ett objekt.
<source lang="java">
public class Program {
     public static int year = 2016; // Statiskt attribut
}

public class OtherProgram { // Klassen otherProgram ligger i samma paket som Program
     int currentYear = Program.year; // Vi tilldelar variabeln currentYear värdet 2016 genom att kalla på klassvariabeln year i klassen Program
     System.Out.println(currentYear); // Detta kommer att skriva ut 2016 på skärmen
}
</source>

= Arv och polymorfism =
Arv är en stor del av objektorienterad programmering. Varje klass består av instruktioner i form av metoder och attribut. Säg att vi har en klass som heter Dog. Varje hund måste kunna äta, gå och sova, så metoderna eat(), walk() och sleep() känns nödvändiga. Men vi nöjer oss inte med att vara så generella som att enbart ha en klass för alla hundar, utan vi vill skapa en specifik klass för just Golden Retrievers, så vi skapar klassen GoldenRetriever som ärver från klassen Dog. Nu är vår klass Dog en superklass och vår klass GoldenRetriever en subklass till Dog. En Golden Retriever gillar en viss typ av mat som andra hundar inte gillar, därför måste vi skriva en ny unik metod av eat() i vår nya subklass. Det vi nu gör kallas för att överskugga (override) en metod. När vi nu kallar på metoden eat() för ett GoldenRetriever-objekt så kommer den klasspecifika metoden att köras och inte den generella i klassen Dog. Däremot om vi kallar på metoden sleep() för ett GoldenRetriever-objekt så kommer den generella metoden för klassen Dog köras, då alla hundar sover på samma sätt och ingen ny klasspecifik metod har skrivits. Det är alltså möjligt att kalla på samtliga metoder i superklassen. Väljer man däremot att skriva över metoden med en subklass-specifik metod så körs den istället.

<b>Klassen Dog</b>
<source lang="java">
public class Dog { 

     public void eat() {
          .....
     }

     public void walk() {
          .....
     }

     public void sleep() {
          .....
     }
}
</source>
<br>
<b>Klassen GoldenRetriever</b>
<source lang="java">
public class GoldenRetriever extends Dog { // För att ärva från en annan klass skriver man "... extends KLASSNAMN" 

     private int age = 7;

     public void eat() { // Metoden overridear metoder eat() i klassen Dog
          .....
     }

     public int getAge() {
          return age;
     }
}
</source>
Om man vill tvinga fram att en subklass måste implementera vissa specifika metoder från dess superklass så gör man de metoderna abstrakta i superklassen. Har man en abstrakt metod i sin superklass så blir hela superklassen <i>abstract</i>. En abstrakt klass kan <u>inte</u> instansieras. I fallet ovan skulle metoden eat() kunna vara ett exempel på en metod som kan vara bra att göra abstrakt, då alla hundar äter olika typ av mat.<br>
<br>
<b>Abstrakta klassen Dog</b>
<source lang="java">
public abstract class Dog { // Klassen Dog är abstrakt och kan inte instansieras

     public abstract void eat(String food); // Metoden är abstrakt och måste implementeras av varje klass som ärver av klassen Dog

     public void walk() {
          .....
     }

     public void sleep() {
          .....
     }
}
</source>
<br>
Polymorfism kommer från grekiskan poly-morf som betyder många former. Säg att vi skriver en metod och vet att vi kommer att få in en hund som inparameter, men inte exakt vilken hund (subklass), det kanske är en Golden Retriever, eller en Tax. I detta fallet så använder vi polymorfism. Då skriver du enbart klassen Dog som inparameter och lämnar det öppet exakt vilken hund-typ som kommer att skickas in. Det är inte förens i körögonblicket som det bestäms.

<source lang="java">
public class Kennel {
     public static void addDog (Dog dog) {
          .....
     }

     public static void main(String[] args) { 
          GoldenRetriever kalle = new GoldenRetriever(); // Vi skapar en ny GoldenRetriever
          Kennel.addDog(kalle); // Vi skickar in en GoldenRetriever in i addDog, vilket är okej då det är en subklass till Dog och är tillåtet enligt polymorfi
     }
}
</source>

[https://sv.wikipedia.org/wiki/Polymorfism_(objektorienterad_programmering) Wikipediaartikeln]

= Loopar =
En loop är ett kodstycke som i sin tur upprepar ett annat kodstycke ett visst antal gånger. Det finns egentligen två loopar som användes mycket i kursen: While-loop och For-loop.

<b> While-loop </b> <br>
En While-loop används då man från början inte vet exakt hur många gånger loopen ska köras, men man kan med ett villkor bestämma det. Så länge villkoret är uppfyllt så körs loopen. Viktigt är att det finns en variabel i villkoret som förändras under varje loop, annars kommer loopen att gå i all evighet. Ett exempel kan vara att man letar efter ett visst värde i en lista, vi slutar loopen när vi hittat värdet. Det programmet kan se ut på följande sätt:

<source lang="java">
ArrayList<Integer> listOfNumbers = new ArrayList<Integer>(); // Vi skapar en ArrayList av Integers (siffror)

add.listOfNumbers(1); // Vi lägger till ett antal siffror i vår lista
add.listOfNumbers(2);
add.listOfNumbers(3);
add.listOfNumbers(4);
add.listOfNumbers(5);

private int counter = 0;

while (listOfNumbers(counter) != 3) {
     ++counter;
}

System.Out.println(counter); // Siffran 3 kommer att skrivas ut i terminalen
</source>
<youtube>E96a4Z9dTXg?showinfo=0</youtube> 
<br> ''(konceptet while-loop är samma för både programspråket C och Java)''
<br>
[https://en.wikipedia.org/wiki/While_loop Wikipediaartikeln] <br>

<br>
<b> For-loop </b> <br>
For-loopen är en typ av While-loop, även den har ett villkor i sig och så länge som villkoret är uppfyllt så körs loopen. For-loopens huvud är uppdelat i tre delar:
<br>
# Deklaration av integer som används som en counter
# Villkor
# Hur countern ska förändras
<br>

Om vi skriver samma exempel som ovan, fast med en for-loop, skulle det kunna se ut såhär:

<source lang="java">
ArrayList<Integer> listOfNumbers = new ArrayList<Integer>(); // Vi skapar en ArrayList av Integers (siffror)

add.listOfNumbers(1); // Vi lägger till ett antal siffror i vår lista
add.listOfNumbers(2);
add.listOfNumbers(3);
add.listOfNumbers(4);
add.listOfNumbers(5);

private int forPrint;

// Vi skapar integens i som börjar med värdet 0. Detta är vår counter
// Så länge villkoret listOfNumbers(i) != 3 så körs loopen
// Varje varv loopen körs så ökar countern med 1
for (int i = 0; listOfNumbers(i) != 3; ++i) { 
   forPrint = i;
}

System.Out.println(forPrint); // Siffran 3 kommer att skrivas ut i terminalen
</source>
<br>
<youtube>77Ra4igHNgM</youtube><br>
''(konceptet while-loop är samma för både programspråket C och Java)''
<br>
[https://en.wikipedia.org/wiki/For_loop Wikipediaartikeln]

= Unified Modelling Language (UML) =
[[File:UML.png|frame|UML-diagram]]
[[File:UML-relation.png|frame| Ett UML-schema beskriver relationen mellan klasser]]
Unified Modeling Language (UML) är ett objektorienterat sätt att modelera system som beskriver hur olika klasser hör ihop. Ett klassdiagram (som du ser till höger) är en beskrivning över en klass, vad klassen heter, vilka attribut/variabler klassen har och dess metoder. Det beskriver också vilken access varje attribut och metod har genom ett "prefix" (tecken) som skrivs innan attributet/metoden. Det beskriver dessutom vilket indata varje metod har, samt om metoden returnerar något data.

{| class="wikitable"
|+Access klassdiagram
|-
|<u>Prefix </u>
|<u>Access</u>
|<u>Explanation</u>
|-
|<b> + </b>
|public
|Synlig för klassen, paketet, subklasser och värld.
|-
|<b> - </b>
|private
|Synlig enbart i klassen
|-
|<b> # </b>
|protected
|Synlig för klassen, paketet och subklasser.
|-
|<b><u>understruken</u></b>
|static
|Ett static attribut behöver inte instanseras för att användas.
|-
|<b><i>italic</i></b>
|abstract
|Klassen kan inte instanseras och innehåller metoder som <u>måste</u> implementeras.
|}

Ett fullt UML-schema beskriver vilka relationer klasserna har till varandra och om en klass ärver eller implementerar en annan klass. Schemat beskriver även om en klass använder, äger eller "har" en annan klass.

[[File:UML-arv.png|left|UML-arv. Animal är superklass som subklasserna Cat och Dog ärver ifrån]]
<br>
<br>
<br>
<br>
<br>
<br>
[https://en.wikipedia.org/wiki/Unified_Modeling_Language Wikipediaartikeln]

= Datastrukturer =

== Träd ==
En trädstruktur bygger på en rotnod som är "grunden" i trädet. Det är i roten som all avsökning börjar och det är även i roten som man tar bort objekt ur trädet. Varje nod innehåller det datat man vill lagra, det kan till exempel vara siffror, filmtitlar, personnummer osv. Noden har sedan en referens i sig som pekar på dess barn. <br>
Ett träd har följande uppdelning: <br>
[[File:Trad1.png|frame|Träd]]
[[File:Trad-full-perfekt-fullstandigt.png|frame|Tre olika typer av träd]]

* <b> Rot: </b> Grundnoden<br>
* <b> Förälder:</b> Förälder till noden under sig <br>
* <b> Barn:</b> Barn till noden över sig <br>
* <b> Syskon: </b> Två noder som har samma förälder <br>
* <b> Gren: </b> Ett träd kan ha flera grenar. Varje gren har en toppnod och en egen trädstruktur <br>
* <b> Löv: </b> Nod som inte har några barn <br>
<br>

Träd delas också in i tre olika kategorier beroende på dess nodstruktur:
*<b> Perfekt träd:</b> Alla nivåer är fyllda. Det vill säga alla noder har två barn, förutom löven
* <b>Fullt binärt träd:</b> När alla noder antingen har noll eller två barn
* <b> Fullständigt binärt träd: </b> Är ett perfekt träd som saknar några av de högraste löven
<br>
<br>
[https://en.wikipedia.org/wiki/Tree_(data_structure) Wikipediaartikeln]

== Heap ==
En heap bygger på en fullstädig trädstruktur där varje nod högst kan ha 2 stycken barn. Det finns två typer av heapar: Maxheap och Minheap.

[[File:Maxheap.png|frame|Maxheap]]
[[File:Minheap.png|frame|Minheap]]
<b> Maxheap </b><br>
* Roten har det största värdet i heapen 
* Varje barn har ett mindre värde än sin förälder
* Vid borttagning tas rotnoden bort. Den ersätts med den sista noden i heapen (noden som är längst till höger i nedersta leveln). Där efter tittar man om nått av barnen är större än den nya roten. Finner man ett barn som är större, byt dem. Där efter fortsätter man titta på barnen och ser om nån av de två nya barnen är större än noden. Är båda barnen större, byt med den största.
* Vid inaddering av en nod, lägg den sist i heapen (dvs på nästa tomma plats, längst ner i heapen, sett från vänster). Där efter, se om noden är större än sin förälder. Om ja, byt plats, om nej stanna. Fortsätt tills noden har hittat sin rätta plats.
[http://visualgo.net/heap.html Maxheap visualisering] <br>

<b> Minheap </b><br>
* Roten har det minsta värdet i heapen
* Varje barn har ett större värde än sin förälder
* Vid borttagning tas rotnoden bort. Den ersätts med den sista noden i heapen (noden som är längst till höger i nedersta leveln). Där efter tittar man om nått av barnen är mindre än den nya roten. Finner man ett barn som är mindre, byt dem. Där efter fortsätter man titta på barnen och ser om nån av de två nya barnen är mindre än noden. Är båda barnen mindre, byt med den minsta.
* Vid inaddering av en nod, lägg den sist i heapen (dvs på nästa tomma plats, längst ner i heapen, sett från vänster). Där efter, se om noden är mindre än sin förälder. Om ja, byt plats, om nej stanna. Fortsätt tills noden har hittat sin rätta plats.
[https://www.cs.usfca.edu/~galles/visualization/Heap.html Minheap visualisering]<br>
<br>
[https://en.wikipedia.org/wiki/Heap_(data_structure) Wikipediaartikeln]

== Binärt sökträd ==
[[File:Binart-soktrad.png|frame|Binärt sökträd]]
Ett binärt sökträd består även det av en trädstruktur, dock inte nödvändigtvis ett fullständig träd. Ett binärt sökträd har följande egenskaper:
* Varje nod har ett värde
* Nodens vänstra barn och alla andra noder i det vänstra benet ska ha ett mindre värde än noden själv
* Nodens högra barn och alla andra noder i det högra benet ska ha ett större värde än noden själv<br>
[https://sv.wikipedia.org/wiki/Bin%C3%A4rt_s%C3%B6ktr%C3%A4d Wikipediaartikeln]

== Kö (Queue) ==
[[File:Queue.png|frame|Queue]]
En kö är precis vad det låter, först in först ut (FIFO, <u>F</u>irst <u>I</u>n <u>F</u>irst <u>O</u>ut). Tänk dig att du är en kassörska. Det kommer in massa kunder som ställer sig i kö och du hjälper dem en efter en precis i den ordningen som de kom in. Det vill säga, det som har väntat längst får också hjälp först. Kommer det en ny kund så placeras denna sist i kön och får vänta tills alla framför har fått hjälp.
<br>
<br>
Metoder som används i en kö:
* <b> front()/peak():</b> Returnerar det värdet som är längst fram i kön
* <b> void enqueue(E):</b> Datat E längst till i slutet av kön
* <b> dequeue():</b> Returnerar och tar bort det värdet som är längst fram i kön
* <b> int size():</b> Returnerar storleken på kön, dvs antal element.
* <b> boolean isEmpty():</b> Returnerar sant om kön är tom, returnerar falskt om kön ej är tom
<br> 
[https://www.cs.usfca.edu/~galles/visualization/QueueLL.html Visualisering av queue (länkad lista)] <br>
[https://www.cs.usfca.edu/~galles/JavascriptVisual/QueueArray.html Visualisering av queue (array)]

== Stack ==
[[File:Stack.png|frame|upright|Stack]]
En stack fungerar som en stapel tallrikar, där varje tallrik representerar ett värde i stacken. Varje gång man lägger till ett ny tallrik (värde) i stacken så hamnar den nya tallriken högst upp. Varje gång man tar en tallrik från stacken så tar man den man senast la, det vill säga sist in, först ut (LIFO, <u>L</u>ast <u>In</u> <u>F</u>irst <u>O</u>ut).
<br>
<br>

Metoder som man använder i en stack:

* <b> top()/peek():</b> Returnerar det elementet som är på toppen av stacken utan att ta bort det
* <b> void push(E):</b> Lägger elementet E på toppen av stacken
* <b> pop():</b> Returnerar och tar bort elementet som ligger på toppen av stacken
* <b> int size():</b> Returnerar storleken på stacken, det vill säga antalet element
* <b> boolean isEmpty():</b> Returnerar sant om stacken är tom, returnerar falskt om den inte är tom
<br>
[https://www.cs.usfca.edu/~galles/visualization/StackLL.html Visualisering av stack (länkad lista)] <br>
[https://www.cs.usfca.edu/~galles/visualization/StackArray.html Visualisering av stack (array)]

== Listor ==
[[File:Enkellankad-lista.png|frame|Enkellänkad lista]]
[[File:Dubbellankad-lista.png|frame|Dubbellänkad lista]]
[[File:Cirkulart-dubbellankad-lista.png|frame|Cirkulärt dubbellänkad lista]]
Det finns olika typer av listor, det som dock är gemensamt för alla listor är att:
# Varje nod innehåller ett data
# Varje nod innehåller en eller flera referenser till samma typ av nod 

Det som skiljer mellan de olika listorna är hur noderna är sammankopplade. <br>
<br>

<b> Enkellänkad lista </b><br>
I en enkellänkad lista har varje nod en referens som refererar på nästkommande nod i listan. Detta gör att det enbart går att komma åt noder/värden som ligger efter den noden man "är på". <br>
<br>

<b> Dubbellänkad lista </b><br>
I en dubbellänkad lista har varje nod två referenser, den ena refererar till noden före och den andra refererar till noden efter. Detta gör det möjligt att komma åt noder både före och efter noden man "är på". <br>
<br>

<b> Cirkulärt dubbellänkad lista </b><br>
En cirkulärt dubbellänkad lista är en dubbellänkad lista där slutnoden (sista noden i listan) är ihopkopplad med den första noden och vice versa. <br>

== Iterator ==

= Traversering =


Traversering innebär att man läser av (och skriver ut) alla noderna i ett träd i en speciell ordning. Det finns 4 olika sätt att traversera: Level-traversering, preorder-traversering, inorder-traversering och postorder-traversering. Ett enkelt sett att tänka vid pre-, in- och postorder är att varje nod är en cirkel med tre stycken kontaktpunkter: Vänster, botten och höger. Beroende på vilken typ av traversering man är ute efter väljer man att fokusera på en av de tre kontaktpunkterna. Varje traversering börjar sedan på rotnodens vänstra sida. Följ därefter vänster ytterkant runt hela trädet tills du är tillbaka vid startläget. Varje gång du stöter på den kontaktpunkten som korresponderar med den traverseringen du gör så skriver du ut värdet i noden.

<b> Levelorder-Traversering </b>  <br>
Vid Levelorder-traversering läser man av noderna och dess värde, från vänster till höger och nivå för nivå. <br>
E, C, H, A, D, F, B, G <br>
<br>

<b> Preorder-Traversering </b><br>
Vid preorder-traversering fokuserar du på vänster kontaktpunkt, det vill säga varje gång du stöter på vänster kontaktpunkt så skriver du ut värdet i noden. <br>
E, C, A, B, D, H, F, G <br>
<br>

<b> Inorder-Traversering </b><br>
Vid inorder-traversering fokuserar du på kontaktpunkten som är under noden. Någonting annat att lägga märke till är att värderna är sorterade från minst till högst.<br>
A, B, C, D, E, F, G, H <br>
<br>

<b> Postorder-Traversering </b><br>
Vid postorder-traversering fokuserar du på höger kontaktpunkt. <br>
B, A, D, C, G, F, H, E <br>

{| class="wikitable"
|-
|[[File:Levelorder-trav.gif|frame|none|Level-traversering <br>
E C H A D F B G]]
|[[File:Preorder-trav.gif|frame|none|Preorder-traversering <br>
E C A B D H F G]]
|[[File:Inorder-trav.gif|frame|none|Inorder-traversering <br>
A B C D E F G H]]
|[[File:Postorder-trav.gif|frame|none|Postorder-traversering <br>
B A D C G F H E]]
|}

= Sorteringsalgoritmer =
En sorteringsalgoritm används för att sortera data. Olika algoritmer är olika effektiva beroende på förhållandena där den ska implementeras. 

== Tidskomplexitet ==
[[File:Ordo.png|frame|Varje for-loop är beroende av inparametern "n" och har tidskomplexiteten O(n). I och med att det är en loop i en loop, där båda looparna är beroende av "n", så blir den totala tidskomplexiteten O(n)*O(n) = O(n<sup>2</sup>).]]
Att bestämma hur snabb en algoritm är genom att ta tid på hur länge den håller på är svårt, både för att mindre algoritmer går otroligt fort och för att olika datorer kan köra en samma algoritm på olika tid beroende på prestanda hos datorn. Vi behöver alltså ett generiskt sätt att mäta hastigheten, oavsett vilken dator den körs på. Det är här tidskomplexitet och Ordo kommer in i bilden. När vi beräknar Ordo (stora O) för en algoritm börjar vi med att bryta ner den i mindre delar och räknar ut de mindre delarnas tidskomplexitet. 
<br>

Samtliga primitiva operationer har tidskomplexitet O(1):
<ol> Jämförelser (2>x)<br>
Aritmetiska operationer (4+x)<br>
Tilldelning (z = i)<br>
Arrayindexering (arrayOfNumbers[3])<br>
Metodretur (return true) <br>
Objektreferering (humanObject.age) <br>
</ol>
<br>
Om antalet primitiva operationer beror på indatats storlek (t.ex i en for-loop där den primitiva operationen i loopen kör n antal gånger) blir tidskomplexiteten O(n), där n = indata. Skulle det vara ytterligare en for-loop i for-loopen, som även den är beroende av indatat = n så får du tidskomplexiteten O(n)*O(n) = O(n<sup>2</sup>).<br>
Vid addering och multiplicering av delkomplexiteten så tar man inte hänsyn till konstanter (O(15n<sup>4</sup>) -> O(n<sup>4</sup>))
<br>
<br>
<b> Addition: </b> Vid addition av Ordo så tar man bara hänsyn till den term som är av högst ordning. Exempel: <br>
O(4n) + <u>O(2n<sup>3</sup>)</u> + O(7n<sup>2</sup>) = O(n<sup>3</sup>) <br>
<br>
<b>Multiplikation: </b> Vid multiplikation av Ordo så adderar du ihop exponenterna i termerna. Exempel: <br>
O(15n<sup>3</sup>)*O(22n<sup>9</sup>) = O(n<sup>12</sup>)<br>
<br>
<b>Kombination: </b> Vid en kombination så tittar du som vanligt först på multiplikationerna, sedan på additionerna. Exempel: <br>
O(n)*O(3) + O(n<sup>2</sup>) + O(n<sup>2</sup>)*O(n) = O(n<sup>3</sup>)

{| class="wikitable" style="width: 100px; height: 50px;"
|+Minst till störst
|-
|<u>Tidskomplexitet </u>
|<u>Benämning</u>
|-
|O(1)
|Konstant 
|-
|O(log(n))
|Logaritmisk
|-
|O(n)
|Linjär
|-
|O(nlog(n))
|
|-
|O(n<sup>2</sup>)
|Kvadratisk
|
|-
|O(n<sup>3</sup>)
|Kubisk
|
|-
|O(2<sup>n</sup>)
|Exponentiell
|
|-
|O(n!)
|Faktoriell
|
|-
|O(n<sup>x</sup>)
|Polynomisk
|}

== Bubble sort ==
[[File:Bubblesort.gif|frame|Bubblesort]]
Bubble sort-algoritmen är en relativt långsam algoritm med en medeltidskomplexitet på O(n<sup>2</sup>). <br>
<br>
<b>Algoritm</b><br>
Vi sorterar minst till vänster, störst till höger.
# Börja i någon av ändarna (detta fallet vänster)
# Jämför de två bredvidliggande värdena. Är vänster större än höger -> Byt plats
# Hoppa ett steg till höger. Upprepa steg 2
# När algoritmen träffar högerkanten, upprepa steg 1. Upprepa detta tills datat är sorterat

Den kallas Bubble Sort för att den "bubblar" upp värdena längst listan tills de hamnar på sin rätta plats. <br> <br>
<b>Stabil?</b> Ja <br>
<b>Tidskomplexitet </b><br>
* Bästa fall: O(n)
* Medelfall: O(n²)
* Värsta fall: O(n²)
<br>
<youtube> 8Kp-8OGwphY </youtube>

== Shaker sort (Cocktail shaker sort) ==
[[file:Shakersort.gif|frame|Shakersort]]
Shaker sort är väldigt lik Bubble sort, med skillnaden att man vänder efter varje "varv" och går  Höger -> Vänster -> Höger -> Vänster osv, lite som en bartender skakar en shaker. <br>
<br>
<b>Algoritm </b> <br>
Vi sorterar minst till vänster, störst till höger.
# Börja i någon av ändarna (detta fallet höger)
# Jämför de två bredvidliggande värdena. Är vänster större än höger -> Byt plats
# Hoppa ett steg till vänster. Upprepa steg 2
# När algoritmen träffar vänsterkanten, hoppa ett steg till höger igen och upprepa steg 2
# Gör detta fram och tillbaka tills datat är sorterat
<br>
<b>Stabil?</b> Ja <br>
<b>Tidskomplexitet</b><br>
* Bästa fall: O(n)
* Medelfall: O(n²)
* Värsta fall: O(n²)
<br>
<youtube>njClLBoEbfI</youtube>.

== Insertionsort ==
[[file:Insertionsort.gif|frame|Insertionsort]]
Vi delar upp datat i en sorterad och en osorterad del. Från början är hela listan osorterad.<br>
<br>
<b>Algoritm</b>
# Titta på det första värdet i den osorterade listan och placera den på rätt ställe i den sorterade listan
# Upprepa steg 1 tills all data är sorterat
<br>
<b>Stabil?</b> Ja <br>
<b>Tidskomplexitet</b> <br>
* Bästa fall: O(n)
* Medelfall: O(n²)
* Värsta fall: O(n²)
<br>
<youtube>DFG-XuyPYUQ</youtube>

== Selectionsort ==
I Selectionsort så delar vi upp datat i en sorterad och en osorterad del. Från början är hela listan osorterad.<br>
<br>
<b>Algoritm</b>
# Leta upp det minsta värdet i den osorterade listan
# Lägg värdet i slutet av den sorterade listan
# Upprepa steg 1 och steg 2 tills hela listan är sorterad
<br>
<b>Exempel:</b> <br>
425916<br>
4259<b>1</b>6 <i> // 1 är minst </i><br>
<u>1</u>259<u>4</u>6 <i> // Byt 1 och 4</i> <br>
1<b>2</b>5946 <i> // 2 är minst </i><br> 
1<u>2</u>5946 <i> // Byt 2 med sig själv </i><br> 
1259<b>4</b>6  <i> // 4 är minst </i><br>
12<u>4</u>9<u>5</u>6 <i> // Byt 4 och 5 </i><br>
1249<b>5</b>6 <i> // 5 är minst </i> <br>
124<u>5</u><u>9</u>6 <i> // Byt 5 och 9 </i> <br>
12459<b>6</b> <i> // 6 är minst </i> <br>
1245<u>6</u><u>9</u> <i> // Byt 6 och 9 </i> <br>
<b>124569</b>
<br>
<br>
<b>Stabil?</b> Nej <br>
<b>Tidskomplexitet</b> <br>
* Bästa fall: O(n²)
* Medelfall: O(n²)
* Värsta fall: O(n²)
<br>
<youtube>f8hXR_Hvybo</youtube>

= Föreläsningar =
<b> Föreläsning 1 </b> <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer Kursinformation] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Java Java] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Loopar Loopar] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Objektorientering Objektorientering] <br>
<br>
<b> Föreläsning 2 </b> <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Konstruktorer Konstruktorer] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Statiska_metoder_och_attribut Statiska metoder och attribut] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Synlighet Synlighet] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Arv_och_polymorfism Arv och polymorfism] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Unified_Modelling_Language_.28UML.29 Unified Modelling Language (UML)] <br>
<br>
<b> Föreläsning 3 </b> <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Abstrakta_datatyper Abstrakta datatyper] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Listor Listor] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Stack Stack] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#K.C3.B6_.28Queue.29 Kö (Queue)] <br>
<br>
<b> Föreläsning 4 </b> <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Interface Interface] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Generiska_klasser Generiska klasser] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Undantag Undantag] <br>
<br>
<b> Föreläsning 5 </b> <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Tidskomplexitet Algoritmanalys (Ordo)] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Insertionsort Insertionsort] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Grafiska_komponenter Grafiska komponenter] <br>
<br>
<b> Föreläsning 6 </b> <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Bubblesort Bubblesort] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Shakersort Shakersort] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Mergesort Mergesort] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Strommar] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Datum] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Formatering] <br>
<br>
<b> Föreläsning 7 </b> <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Selectionsort Selectionsort] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Shellsort Shellsort] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Quicksort Quicksort] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Grafiska_användargranssnitt Grafiska användargränssnitt] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Swing Swing] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Layout] <br>
<br>
<b> Föreläsning 8 </b> <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Träd Träd] <br>
[http://studieboken.se/TDDC30_-_Programmering_i_Java,_datastrukturer_och_algoritmer#Traversering Traversering] <br>
<br>

= Annat material =
== Sammanfattningar ==
<div class="opennewtab">[[Media:Sammanfattning-TDDC30.pdf|Sammanfattning]]</div>

<div class="opennewtab">[[Media:Sammanfattning_TDDC30_Programmering_i_Java,_datastrukturer_och_algoritmer.pdf|Sammanfattning TDDC30 - Programmering i Java, datastrukturer och algoritmer]]</div>

== Tentor ==
[https://www.ida.liu.se/~TDDC30/current/exam/ Tentor (LIU)]

== Tentaanalys ==
[[File:Tenta-analys.png|Left|Tentaanalys]]

== Länkar ==
[http://kdb-5.liu.se/liu/lith/studiehandboken/svkursplan.lasso?&k_budget_year=2016&k_kurskod=TDDC30 Kursplan]<br>
[http://www4.student.liu.se/tentaresult/?kurskod=TDDC30&provkod=&datum=&kursnamn=&sort=0&search=S%F6k Tentastatistik]<br>
[https://www.ida.liu.se/~TDDC30/ Kurshemsida]<br>

= Se även =
[[Industriell ekonomi - Linköpings universitet]] <br>
[[TAOP37 - Optimeringslära, fortsättningskurs]] <br>
[[TPPE98 - Ekonomisk analys: Ekonomisk teori]]