Chapter 5: linked list data structure

DATA STRUCTURE Chapter 5: Linked List Prepared & Presented by Mr. Mahmoud R. Alfarra 2011-2012 College of Science & Technology Dep. Of Computer Science & IT BCs of Information Technology http://mfarra.cst.ps

Out Line  Self- Referential class  What is Linked List?  Insert & delete elements  Print data  Sorting data  Search about data  Collection of linked list 2

Self- Referential class  Self- referential class is a class which contains an object of it self.  These concept uses to link objects with others. 3 class Node { private int data; private Node next; public Node( int d ) { // some code } } next object is an object of Node class, so this class is a self referential class

What is linked list ? 4 ‫البيانات‬ ‫تراكيب‬ ‫مساق‬ ‫إعداد‬ ‫العلمية‬ ‫المادة‬ / ‫أ‬ . ‫ا‬ َّ‫الفــر‬ ‫رفيق‬ ‫محمود‬  A linked list is a collection of class objects called nodes.  Each node is linked to its successor node in the list using a reference to the successor node.  A node is made up of a field for storing data and the field for the node reference.  The reference to another node is called a link.

Ahmad 25 year Developer Elements of list ? 5  A list or linked list composed of number of objects of a class, if you want to develop a list of employees, you will insert many objects of employees to your list, and so on … Ali 28 year Lecturer Ola 27 year Designer ....

Application: List of cars 6 Car Class ListCar Class CarSystem Class In this class we will create an object of ListCar class, and then manipulates the list using all operations. The class of linked list members and operation, this class simulate the list of any thing, the object of this class will be created and used in the class of CarSystem. A self referential class called Car, contains the attributes and behavior of any car. 1 2 3

1- Class Car 7 1. class Car 2. { 3. public int id; 4. public String location; 5. public String type; 6. public Car next; 7. public Car() 8. { 9. id = 0; 10. location = "Gaza"; 11. type = "Private"; 12. } 13. }

2- class ListCar 8 1. class ListCar 2. { 3. private int length ; // instance variable to count number of elements in the list 4. public Car head; // Object will point to the first element in the list 5. public ListCar() 6. { 7. lenght = 0; 8. head = null; // initially the head points to nothing 9. } 10. // Here the manipulated operation will be developed 11. }

Create object of List Car 9 1. static void Main(string[] args) 2. { 3. ListCar list1 = new ListCar(); 4. }  This objet of list will be manipulated using the operations.

Insert at the first position Data 1 Head Data 2 Data 3 Data n ….. null New data 1 2

Insert at the first position 11 1. class ListCar { 2. private int lenght ; 3. public Car head; 4. public ListCar() { 5. lenght = 0; 6. head = null; } 7. public void addAtFront(Car inserted) { 8. Car newc = new Car(); 9. newc = inserted; 10. newc.next = head; 11. lenght++; 12. head = newc; } 13. } Please Note that: all codes in the PPT files of this course are not completely, so you must depend on the practical files. The current codes are only to explain the main idea

Insert at the last position Data 1 Front Data 2 Data 3 Data n ….. null New data 2 null 1 Back X 1 Back X 1 Back X 1 Back X

Insert at the last position 13 ‫البيانات‬ ‫تراكيب‬ ‫مساق‬ ‫إعداد‬ ‫العلمية‬ ‫المادة‬ / ‫أ‬ . ‫ا‬ َّ‫الفــر‬ ‫رفيق‬ ‫محمود‬ 1. class ListCar { 2. …. 3. public void addAtFront(Car inserted) { 4. … } 5. public void addAtback(Car inserted) { 6. Car newc = new Car(); 7. Car back = head; 8. while (back.next != null) 9. back = back.next; 10. back.next = newc; 11. newc.next = null; 12. length ++; 13. } 14. } If the list is empty? What will be do?

Delete the first elements Data 1 Head Data 2 Data 3 Data n ….. null X

Delete the first elements 15 ‫البيانات‬ ‫تراكيب‬ ‫مساق‬ ‫إعداد‬ ‫العلمية‬ ‫المادة‬ / ‫أ‬ . ‫ا‬ َّ‫الفــر‬ ‫رفيق‬ ‫محمود‬ 1. class ListCar { 2. …. 3. public void addAtFront(Car inserted) { 4. … } 5. public void addAtback(Car inserted) { 6. … } 7. public void RemoveFromFront() 8. { 9. head = head.next; 10. lenght--; 11. } 12.}

Delete the last elements Data 1 Front Data 2 Data 3 Data n ….. null Back current × 1 2

Delete the last elements 17 ‫البيانات‬ ‫تراكيب‬ ‫مساق‬ ‫إعداد‬ ‫العلمية‬ ‫المادة‬ / ‫أ‬ . ‫ا‬ َّ‫الفــر‬ ‫رفيق‬ ‫محمود‬ 1. class ListCar { 2. …. 3. public void addAtFront(Car inserted) { … } 4. public void addAtback(Car inserted) { … } 5. public void RemoveFromFront() { … } 6. public void RemoveFromback() { 7. Car current = head; 8. Car back = head.next; 9. while (back.next != null) { 10. back = back.next; 11. current = current.next; } 12. current.next = null; 13. lenght--; } 14.}

Insert a new element at position k Data 1 Head Data 2 Data 3 Data n ….. null New data 1 Will be inserted at position 2 (the third element) 0 1 2 n 2 × current

Insert a new element at position k 19 ‫البيانات‬ ‫تراكيب‬ ‫مساق‬ ‫إعداد‬ ‫العلمية‬ ‫المادة‬ / ‫أ‬ . ‫ا‬ َّ‫الفــر‬ ‫رفيق‬ ‫محمود‬ 1. class ListCar { 2. …. 3. public void RemoveFromback() { …. } 4. public void addAtPosition(Car inserted, int position) { 5. Car current = head; 6. Car newc = inserted; 7. int counter =0; 8. while (counter < position) { 9. current = current.next; 10. counter++; } 11. newc.next = current.next; 12. current.next = newc; 13. lenght++; } 14.}

Insert a new element based on an order Data 1 Head Data 2 Data 3 Data n ….. null New data 1 Example: Will be inserted after the value x 0 1 2 n 2 × current Front

Insert a new element based on an order 21 ‫البيانات‬ ‫تراكيب‬ ‫مساق‬ ‫إعداد‬ ‫العلمية‬ ‫المادة‬ / ‫أ‬ . ‫ا‬ َّ‫الفــر‬ ‫رفيق‬ ‫محمود‬ 1. class ListCar { 2. …. 3. public void addAtPosition(Car inserted, int position) { … } 4. public void addAtvalue(Car inserted, int value) { 5. Car current = head; 6. Car front = head; 7. Car newc = inserted; 8. while (current.value < value) { 9. front = current; 10. current = current.next; } 11. newc.next = current; 12. front.next = newc; 13. lenght++; } 14.} •The new element will be inserted in its right position based on its value. • Note that the list is ordered.

Delete an element from position Data 1 Head Data k- 1 Data k Data n null Current Data k+1 1 × × Front

Delete an element from position 23 ‫البيانات‬ ‫تراكيب‬ ‫مساق‬ ‫إعداد‬ ‫العلمية‬ ‫المادة‬ / ‫أ‬ . ‫ا‬ َّ‫الفــر‬ ‫رفيق‬ ‫محمود‬ 1. class ListCar { 2. …. 3. public void RemovefromPosition(int position) { 4. Car current = head; 5. Car front = head; 6. int counter = 0; 7. while (counter < position) { 8. current = front; 9. front = front.next; 10. counter++; } 11. current.next = front.next; 12. lenght--; } 13.} Practice 1: re- code it to delete the node which has value x

Print the data … 24 1. class ListCar { 2. …. 3. public void PrintData() { 4. Car current = head; 5. Console.WriteLine("The Data of List are"); 6. int counter = 1; 7. while (current != null) { 8. Console.WriteLine("The Data of element # "+counter); 9. Console.WriteLine("======================="); 10. Console.WriteLine("ID " + current.id); 11. Console.WriteLine("Location " + current.location); 12. Console.WriteLine("Type " + current.type); 13. Console.WriteLine("======================="); 14. current = current.next; 15. counter++; } 16. }}

Sort linked List by swapping objects (bubble) Data 1 Head Data k- 1 Data k Data n null Data k+1 Current b c d Second e Temp 1 a 2 3 Data 1 Head Data k Data k-1 Data n null Data k+1 b c d e a 4

Sort linked List by swapping objects (bubble) Data 1 Head Data k- 1 Data k Data n null Data k+1 Current b c d Second e Temp 1 a 2 3 4 Node current = head; Node temp; for (int i = 0; i < lenght; i++) { Car current = head; while (current.Next != null) { temp.data = current.Next.data; current.Next.Value = current.Value; current.Value = temp; current = current.Next.Next; } }

Sort linked List by swapping values (bubble) Data 1 Head Data k- 1 Data k Data n null Data k+1 Current b c d e a Front Tempalue = Current.value; Current.value = front.value; Front.value = tempvalue; . . .

Sort linked List by swapping values (bubble) 28 ‫البيانات‬ ‫تراكيب‬ ‫مساق‬ ‫إعداد‬ ‫العلمية‬ ‫المادة‬ / ‫أ‬ . ‫ا‬ َّ‫الفــر‬ ‫رفيق‬ ‫محمود‬ 1. class ListCar { 2. public void bubSort() { 3. for (int i = 0; i < lenght; i++) { 4. Car current = head; 5. while (current.next != null) { 6. if (current.value > current.next.value) { 7. int TempValue = current.value; 8. int TempId = current.id; 9. String TempLocation = current.location; 10. current.value = current.next.value; 11. current.id = current.next.id; 12. current.location = current.next.location; 13. current.next.value = TempValue; 14. current.next.id = TempId; 15. current.next.location = TempLocation; } 16. current = current.next; } } } 17. }

Search about data !! 1. class ListCar { 2. public Car Find(int WantedVlaue ) 3. { 4. Car current = head; 5. int flag = -1; 6. while (current != null) { 7. if (current.value == WantedVlaue) { 8. flag = 1; 9. break; } 10. current = current.next; } 11. if (flag == 1) 12. return current; 13. else 14. return null; } 15. }

Collection of linked list 30  C# contains the collection of linked list in the name space called: Namespace: System.Collections.Generic  It has a full package of methods and members to manage its data. Case Study :using the reference book, write a completed application to simulate the linked list of PCs.

Thank You … 31 Remember that: question is the key of knowledge

Ahl Eljanna   ٍ ‫ني‬ِ ‫َم‬‫أ‬ ٍ ‫ام‬َ ‫ق‬َ ‫م‬ ِ ‫ِف‬ َ ‫ني‬ِ ‫َّق‬‫ت‬ُ ‫ْم‬‫ل‬‫ا‬ َّ ‫ن‬ِ‫إ‬ ( ):: ٍ ‫ون‬ُ‫ي‬ُ‫ع‬َ ‫و‬ ٍ ‫َّات‬‫ن‬َ ‫ج‬ ِ ‫ِف‬ ::( ) َ ‫ر‬ْ‫ب‬َ‫ت‬ْ ‫س‬ِ‫إ‬َ ‫و‬ ٍ ‫س‬ُ ‫د‬‫ن‬ُ ‫س‬ ْ ‫ن‬ِ ‫م‬ َ ‫ن‬‫و‬ُ ‫س‬َ‫ب‬ْ‫ل‬َ‫ي‬ َ ‫ني‬ِ‫ل‬ِ‫ب‬‫ا‬َ ‫ق‬َ‫ت‬ُ ‫م‬ ٍ ‫ق‬ )::( َ ‫ذ‬َ ‫ك‬ َ ‫ك‬ِ‫ل‬ ٍ ‫ني‬ِ ‫ع‬ ٍ ‫ر‬‫و‬ُِ ‫ِب‬ ْ ‫م‬ُ ‫اه‬َ‫ن‬ْ ‫ج‬َّ ‫و‬َ ‫ز‬َ ‫و‬ )::( ُ‫ع‬ْ ‫د‬َ‫ي‬ ِ‫اك‬َ‫ف‬ ِِّ ‫ل‬ُ ‫ك‬ِ‫ب‬ ‫ا‬َ ‫يه‬ِ‫ف‬ َ ‫ن‬‫و‬ َ ‫ني‬ِ‫ن‬ِ ‫آم‬ ٍ ‫ة‬َ ‫ه‬ )::( 32

Chapter 5: linked list data structure

More Related Content

What's hot

Similar to Chapter 5: linked list data structure

More from Mahmoud Alfarra

Recently uploaded

Chapter 5: linked list data structure