Lecture 14
Linked Lists
CSE 1322
4/26/2018
14-1
LinkedLists
Dynamic data structurescan grow and shrink at execution time.Alinked listis a linear collection (i.e., a sequence) ofnodes, connected by reference links (“chained together”).It can be singly or doubly linkedA linked list is appropriate when the number of data elements is unpredictable.Linked lists become full only when the system has insufficient memory.
4/26/2018
14-2
Nodes
Aself-referential classcontains a member that refers to an object of the same class type.In the class declarationNextreferences an object of typeNode, an object of the same type being declared.Nextis referred to as alink.class Node{public string data;public Node next ;}
4/26/2018
14-3
A Linked List
A linked list can be thought of as a chain of linked nodes.A node is an object with two attributes:datathe location of the next node in the chainA backslash indicates a null link.Not setting the link in the last node of a list tonullis a logic error.
4/26/2018
14-4
Common tasks include:
Inserting to the frontInserting to the endInserting in between the front/endDeletingSearchingSortingEach of these tasks takes different amounts of time depending upon how the linked list is implemented
4/26/2018
14-5
TheinsertMethod
Theinsertmethod performs the following steps:1. Instantiate a new node containing theintto be inserted.2. Attach that node at the beginning of the list, that is, make that node point to the previous head node. If the list originally was empty and the previous head node has the valuenull, then thenextfield of the new node is given the valuenull.3. Indicate that the new node is now the head of the list, that is, makeheadpoint to the new node.
4/26/2018
14-6
TheinsertMethod
The original list:The new node isinstantiated:The new node isattached to thebeginning of the list:headnow points tothe new node:
4/26/2018
14-7
ThedeleteMethod
To find the node to delete, wetraversethe list. Traversing a list means to loop through the list, visiting each node in order.Three outcomes are possible:The item is found and is not the head of the list.The item is found and is the head of the list.The item is not found, and therefore, cannot be deleted.As we traverse the list, we maintain a reference to the previous node, because we will need to connect that node to the node following the deleted node.
4/26/2018
14-8
Deleting an Item That is Not the Head
The list beforedeleting the itemwith the value 8:Thepreviousnodeis connected to thenode aftercurrent:
4/26/2018
14-9
Deleting an Item That is the Head
The list before deletingthe item whosevalueis 7:The link from the firstnode becomes thenewhead:
4/26/2018
14-10
Testing a Linked List Class
Be sure to test all possibilities.Insert:inserting into an empty listinserting into a nonempty listDelete:attempting to delete from an empty listdeleting the first item in the listdeleting the last item in the listdeleting an item in the middle of the list.attempting to delete an item not in the list
4/26/2018
14-11
A linked list of ints -- the node and constructor
publicclassLinkListClass{private Node first;class Node{publicintnum;public Node next;}publicLinkListClass(){first=null;}
4/26/2018
14-12
A linked list of ints -- add front
public voidaddNode(int n){NodenewNode= new Node();newNode.num=n;newNode.next=first;first=newNode;}
4/26/2018
14-13
A linked list of ints -- add back
public voidaddBack(int n){Node temp= new Node();temp.num=n;Node current =first;while(current.next!=null)current=current.next;current.next=temp;}
4/26/2018
14-14
A linked list of ints -- remove
public void remove(int n){Nodecurr=first;Nodeprev=curr;if(curr.num==(n)){first=curr.next;return;}while(curr.num!=(n)){prev=curr;curr=curr.next;if(curr==null)return;}prev.next=curr.next;}
4/26/2018
14-15
A linked list of ints -- display
public String display(){Node current= first;String data= "";while(current.next!=null){data+=" "+current.num+" --> " ;current=current.next;}data+=" "+current.num+" --> " ;return data;}
4/26/2018
14-16
A linked list of ints -- display
public String display(){Node current= first;String data= "";while(current.next!=null){data+=" "+current.num+" --> " ;current=current.next;}data+=" "+current.num+" --> " ;return data;}
4/26/2018
14-17
Java Client
LinkListClassLL = newLinkListClass();System.out.println(LL);LL.addNode(5);LL.addNode(7);LL.addNode(1);LL.addBack(4);System.out.println("display1 "+ LL+ " "+LL.display());LL.remove(5);System.out.println("display2 "+ LL+ " "+LL.display());LL.remove(9);System.out.println("display3 "+ LL+ " "+LL.display());LL.addNode(8);System.out.println("display4 "+ LL+ " "+LL.display());LL.addNode(3);System.out.println("display5 "+ LL+ " "+LL.display());
4/26/2018
14-18
C# Client
LinkListClassLL = newLinkListClass();Console.WriteLine(LL);LL.addNode(5);LL.addNode(7);LL.addNode(1);LL.addBack(4);Console.WriteLine("display1 " +LL.display());LL.remove(5);Console.WriteLine("display2 " +LL.display());LL.remove(9);Console.WriteLine("display3 " +LL.display());LL.addNode(8);Console.WriteLine("display4 " +LL.display());LL.addNode(3);Console.WriteLine("display5 " +LL.display());
4/26/2018
14-19
0
Embed
Upload