Tajseer.files.wordpress.com



Chapter-3 Linked ListsLinked List:Linked list is a very common linear data structure used to store similar data in memory. Linked list is a collection of Nodes. Link list is not constrained to be stored in adjacent memory location like Array. If we want to maintain the ordered list that allows quick insertion and deletions we use Linked Data nextORStructure of Node: infonextNode: It contains information (data) and address (link) of the next NodeOperations on linked listCreate. Display.Insertion. (a) Adding to Head (b) Adding to TailDeletion.(a) Deleting from Head (b) Deleting from Tail (c) Deleting from MiddleSearch.Types of Linked List:Singly Linked ListDoubly Linked ListCircular Linked ListSingly Linked List:A sequence of nodes is the most frequently used implementation of a linked list, which is a data structure composed of nodes, each node holding some information and a reference to another node in the list. If a node has a link only to its successor in this sequence, the list is called a singly linked list.First/Head10200203004060070Last/Tailnull100100200300600A singly linked list implementation uses two classes: one class, IntNode, for nodes of the list, and another, IntSLList, for access to the list. The class IntSLList define two data fields, head and tail, which are references to the first and the last nodes of a list.Insertion Algorithms:Adding a new node at the beginning of a linked list is performed in four steps:An empty node is created. The node’s info field is initialized to a particular integer.The next field becomes a reference to the first node on the list.The new node precedes all the nodes on the list.In Java we write:public void addToHead(int el){head=new IntNode(el,head);if(tail==null)tail=head;}Adding a new node to the end of a linked list is performed in five steps:An empty node is created. The node’s info field is initialized to an integer el.The next field is set to null.The next field of the last node of the list a reference to the newly created node.The new node follows all the nodes of the list.In Java we write:public void addToTail(int el){if(!isEmpty()){tail.next=new IntNode(el);tail=tail.next;}elsehead=tail=new IntNode(el);}Deletion Algorithms:deleteFromHead(): In this operation the information from the first node is temporarily stored in a local variable el, and then head is reset so that the second node becomes the first node.In Java we write:public int deleteFromHead(){int el=;if(head==tail)head=tail=null;elsehead=head.next;return el;}deleteFromTail(): In this operation the information from the last node is temporarily stored in a local variable el, and then after removing a node, tail should refer to the new tail of the list, that is, tail has to be moved backward by on node.In Java we write:public int deleteFromTail(){int el=;if(head==tail)head=tail=null;else{IntNode tmp;for(tmp=head; tmp.next!=tail; tmp=tmp.next);tail=tmp;tail.next=null;}return el;}Search:The insertion and deletion operations modify linked list. The searching operation scans an existing list to learn whether or not a number is in it. We implement this operation with the Boolean method isInLIst().public boolean isInList(int el){IntNode tmp;for(tmp=head;tmp!=null && !=el;tmp=tmp.next);return tmp!=null;}INSERTION IN TO THE LINKED LIST:At the BeginningAt the EndAt an Arbitrary Location (any where in the center)Insertion At the Beginning:Example: Head / First Node10102620102840103070NULL 102410241026 1028Last Node /Tail 1030Solution10102620102840103070NULL Head 204010241026 1028Last Node /Tail 1030901024First Node 2040Insertion At the End: Head / First NodeExample:10102620102840103070NULL 102410241026 1028Last Node /Tail 1030Solution Head / First NodeLast Node /Tail1024101026201028401030701140 102410241026 1028 103080NULL1140Insertion At an Arbitrary Location (any where in the center): Head / First NodeExample:10102620102840103070NULL 102410241026 1028Last Node /Tail 1030Solution Head / First Node10102620332540103070NULL 102410241026 1028Last Node /Tail 10305510283325DELETION FROM THE LINKED LIST:At the BeginningAt the EndAt an Arbitrary Location (any where in the center)Delete from the Beginning:Example:10102620102840103070NULL Head 204010241026 1028Last Node /Tail 1030901024First Node 2040Solution Head / First Node10102620102840103070NULL 102410241026 1028Last Node /Tail 1030Delete from the End:Example80NULL Last Node /Tail1024101026201028401030701140 102410241026 1028 1030 Head / First Node1140 Head / First NodeSolution:10102620102840103070NULL 102410241026 1028Last Node /Tail 1030Delete from an Arbitrary Location (any where in the center): Head / First NodeExample:10102620332540103070NULL 102410241026 1028Last Node /Tail 10305510283325 Head / First NodeSolution:10102620102840103070NULL 102410241026 1028Last Node /Tail 1030Insertion, Display, Search & Deletion (Links list Implementation)class IntNode //Creates New Node{public int info;public IntNode next;public IntNode(int i){this(i,null);}public IntNode(int i,IntNode n){info=i;next=n;}}//End of class IntNodeclass IntSLList{private IntNode head,tail;public IntSLList(){head=tail=null;}public boolean isEmpty(){return head==null;}public void addToHead(int el){head=new IntNode(el,head);if(tail==null)tail=head;}public void addToTail(int el){if(!isEmpty()){tail.next=new IntNode(el);tail=tail.next;}elsehead=tail=new IntNode(el);}public int deleteFromHead(){int el=;if(head==tail)head=tail=null;elsehead=head.next;return el;}public int deleteFromTail(){int el=;if(head==tail)head=tail=null;else{IntNode tmp;for(tmp=head; tmp.next!=tail; tmp=tmp.next);tail=tmp;tail.next=null;}return el;}public void printAll(){for(IntNode tmp=head;tmp!=null;tmp=tmp.next)System.out.print(+"\t");System.out.println();}public boolean isInList(int el){IntNode tmp;for(tmp=head;tmp!=null && !=el;tmp=tmp.next);return tmp!=null;}public void delete(int el){if(!isEmpty()){if(head==tail && el==)head=tail=null;else if(el==)head=head.next;else{IntNode pred,tmp;for(pred=head,tmp=head.next;tmp!=null&&!=el;pred=pred.next,tmp=tmp.next);if(tmp!=null){pred.next=tmp.next;if(tmp==tail)tail=pred;}}}}}//End of class IntSLListclass Test{public static void main(String args[]){//IntNodeIntSLList s=new IntSLList();System.out.println("Elements in the Linked List are: ");s.addToHead(10);s.addToTail(20);s.addToTail(30);s.addToTail(50);s.addToHead(80);s.addToHead(90);s.printAll();System.out.println(s.isInList(30));s.delete(30);System.out.println("Elements after delete 30 are: ");s.printAll();s.deleteFromHead();s.printAll();s.deleteFromTail();s.printAll();}}Doubly linked listIt is linked data structure which has has two reference fields. One to successor and another to predecessor.Example:First/Head10006102610247102810268Last/Tailnull 1000 1024 1026 1208Circular linked listCircular linked list is type of linked list used in data structure where address of 1st node is stored in the link part of last node.Example: ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download