Introduction To Data Structure

 2.1 Simple Array Implementation of Lists


Obviously all of these instructions can be implemented just by using an array. Even if the array is dynamically allocated, an estimate of the maximum size of the list is required. Usually this requires a high over-estimate, which wastes considerable space. This could be a serious limitation, especially if there are many lists of unknown size.

An array implementation allows print_list and find to be carried out in linear time, which is as good as can be expected, and the find_kth operation takes constant time. However, insertion and deletion are expensive. For example, inserting at position 0 (which amounts to making a new first element) requires first pushing the entire array down one spot to make room, whereas deleting the first element requires shifting all the elements in the list up one, so the worst case of these operations is O(n). On average, half the list needs to be moved for either operation, so linear time is still required. Merely building a list by n successive inserts would require quadratic time.

Because the running time for insertions and deletions is so slow and the list size must be known in advance, simple arrays are generally not used to implement lists.

2.1.2  Linked Lists

In order to avoid the linear cost of insertion and deletion, we need to ensure that the list is not stored contiguously, since otherwise entire parts of the list will need to be moved. Figure 2.1 shows the general idea of a linked list.

The linked list consists of a series of structures, which are not necessarily adjacent in memory. Each structure contains the element and a pointer to a structure containing its successor. We call this the next pointer. The last cell's next pointer points to ; this value is defined by C and cannot be confused with another pointer. ANSI C specifies that is zero.


Recall that a pointer variable is just a variable that contains the address where some other data is stored. Thus, if p is declared to be a pointer to a structure, then the value stored in p is interpreted as the location, in main memory, where a structure can be found. A field of that structure can be accessed by pfield_name, where field_name is the name of the field we wish to examine. Figure 2.3 shows the actual representation of the list in Figure 2.1. The list contains five structures, which happen to reside in memory locations 1000, 800, 712, 992, and 692 respectively. The next pointer in the first structure has the value 800, which provides the indication of where the second structure is. The other structures each have a pointer that serves a similar purpose. Of course, in order to access this list, we need to know where the first cell can be found. A pointer variable can be used for this purpose. It is important to remember that a pointer is just a number. We will draw pointers with arrows, because they are more illustrative.








































Figure 2.4 Insertion into a linked list

To execute print_list(L) or find(L,key), we merely pass a pointer to the first element in the list and then traverse the list by following the next pointers. This operation is clearly linear-time, although the constant is likely to be larger than if an array implementation were used. The find_kth operation is no longer quite as efficient as an array implementation; find_kth(L,i) takes O(i) time and works by traversing down the list in the obvious manner. In practice, this bound is pessimistic, because frequently the calls to find_kth are in sorted order (by i). As an example, find_kth(L,2), find_kth(L,3), find_kth(L,4), find_kth(L,6) can all be executed in one scan down the list.

The delete command can be executed in one pointer change. Figure 3.3 shows the result of deleting the third element in the original list.

The insert command requires obtaining a new cell from the system by using an malloc call (more on this later) and then executing two pointer maneuvers. The general idea is shown in Figure 3.4. The dashed line represents the old pointer.

2.1.3. Programming Details

The description above is actually enough to get everything working, but there are several places where you are likely to go wrong. First of all, there is no really obvious way to insert at the front of the list from the definitions given. Second, deleting from the front of the list is a special case, because it changes the start of the list; careless coding will lose the list. A third problem concerns deletion in general. Although the pointer moves above are simple, the deletion algorithm requires us to keep track of the cell before the one that we want to delete.




















































































































































































No comments:

Post a Comment

Labels

PROJECTS 8086 PIN CONFIGURATION 80X86 PROCESSORS TRANSDUCERS 8086 – ARCHITECTURE Hall-Effect Transducers INTEL 8085 OPTICAL MATERIALS BIPOLAR TRANSISTORS INTEL 8255 Optoelectronic Devices Thermistors thevenin's theorem MAXIMUM MODE CONFIGURATION OF 8086 SYSTEM ASSEMBLY LANGUAGE PROGRAMME OF 80X86 PROCESSORS POWER PLANT ENGINEERING PRIME MOVERS 8279 with 8085 MINIMUM MODE CONFIGURATION OF 8086 SYSTEM MISCELLANEOUS DEVICES MODERN ENGINEERING MATERIALS 8085 Processor- Q and A-1 BASIC CONCEPTS OF FLUID MECHANICS OSCILLATORS 8085 Processor- Q and A-2 Features of 8086 PUMPS AND TURBINES 8031/8051 MICROCONTROLLER Chemfet Transducers DIODES FIRST LAW OF THERMODYNAMICS METHOD OF STATEMENTS 8279 with 8086 HIGH VOLTAGE ENGINEERING OVERVOLATGES AND INSULATION COORDINATION Thermocouples 8251A to 8086 ARCHITECTURE OF 8031/8051 Angle-Beam Transducers DATA TRANSFER INSTRUCTIONS IN 8051/8031 INSTRUCTION SET FOR 8051/8031 INTEL 8279 KEYBOARD AND DISPLAY INTERFACES USING 8279 LOGICAL INSTRUCTIONS FOR 8051/8031 Photonic Transducers TECHNOLOGICAL TIPS THREE POINT STARTER 8257 with 8085 ARITHMETIC INSTRUCTIONS IN 8051/8031 LIGHTNING PHENOMENA Photoelectric Detectors Physical Strain Gage Transducers 8259 PROCESSOR APPLICATIONS OF HALL EFFECT BRANCHING INSTRUCTIONS FOR 8051/8031 CPU OF 8031/8051 Capacitive Transducers DECODER Electromagnetic Transducer Hall voltage INTEL 8051 MICROCONTROLLER INTEL 8251A Insulation Resistance Test PINS AND SIGNALS OF 8031/8051 Physical Transducers Resistive Transducer STARTERS Thermocouple Vacuum Gages USART-INTEL 8251A APPLICATIONs OF 8085 MICROPROCESSOR CAPACITANCE Data Transfer Instructions In 8086 Processors EARTH FAULT RELAY ELECTRIC MOTORS ELECTRICAL AND ELECTRONIC INSTRUMENTS ELECTRICAL BREAKDOWN IN GASES FIELD EFFECT TRANSISTOR (FET) INTEL 8257 IONIZATION AND DECAY PROCESSES Inductive Transducers Microprocessor and Microcontroller OVER CURRENT RELAY OVER CURRENT RELAY TESTING METHODS PhotoConductive Detectors PhotoVoltaic Detectors Registers Of 8051/8031 Microcontroller Testing Methods ADC INTERFACE AMPLIFIERS APPLICATIONS OF 8259 EARTH ELECTRODE RESISTANCE MEASUREMENT TESTING METHODS EARTH FAULT RELAY TESTING METHODS Electricity Ferrodynamic Wattmeter Fiber-Optic Transducers IC TESTER IC TESTER part-2 INTERRUPTS Intravascular imaging transducer LIGHTNING ARRESTERS MEASUREMENT SYSTEM Mechanical imaging transducers Mesh Current-2 Millman's Theorem NEGATIVE FEEDBACK Norton's Polarity Test Potentiometric transducers Ratio Test SERIAL DATA COMMUNICATION SFR OF 8051/8031 SOLIDS AND LIQUIDS Speed Control System 8085 Stepper Motor Control System Winding Resistance Test 20 MVA 6-digits 6-digits 7-segment LEDs 7-segment A-to-D A/D ADC ADVANTAGES OF CORONA ALTERNATOR BY POTIER & ASA METHOD ANALOG TO DIGITAL CONVERTER AUXILIARY TRANSFORMER AUXILIARY TRANSFORMER TESTING AUXILIARY TRANSFORMER TESTING METHODS Analog Devices A–D BERNOULLI’S PRINCIPLE BUS BAR BUS BAR TESTING Basic measuring circuits Bernoulli's Equation Bit Manipulation Instruction Buchholz relay test CORONA POWER LOSS CURRENT TRANSFORMER CURRENT TRANSFORMER TESTING Contact resistance test Current to voltage converter DAC INTERFACE DESCRIBE MULTIPLY-EXCITED Digital Storage Oscilloscope Display Driver Circuit E PROMER ELPLUS NT-111 EPROM AND STATIC RAM EXCITED MAGNETIC FIELD Electrical Machines II- Exp NO.1 Energy Meters FACTORS AFFECTING CORONA FLIP FLOPS Fluid Dynamics and Bernoulli's Equation Fluorescence Chemical Transducers Foil Strain Gages HALL EFFECT HIGH VOLTAGE ENGG HV test HYSTERESIS MOTOR Hall co-efficient Hall voltage and Hall Co-efficient High Voltage Insulator Coating Hot-wire anemometer How to Read a Capacitor? IC TESTER part-1 INSTRUMENT TRANSFORMERS Importance of Hall Effect Insulation resistance check Insulator Coating Knee point Test LEDs LEDs Display Driver LEDs Display Driver Circuit LM35 LOGIC CONTROLLER LPT LPT PORT LPT PORT EXPANDER LPT PORT LPT PORT EXTENDER Life Gone? MAGNETIC FIELD MAGNETIC FIELD SYSTEMS METHOD OF STATEMENT FOR TRANSFORMER STABILITY TEST METHODS OF REDUCING CORONA EFFECT MULTIPLY-EXCITED MULTIPLY-EXCITED MAGNETIC FIELD SYSTEMS Mesh Current Mesh Current-1 Moving Iron Instruments Multiplexing Network Theorems Node Voltage Method On-No Load And On Load Condition PLC PORT EXTENDER POTIER & ASA METHOD POWER TRANSFORMER POWER TRANSFORMER TESTING POWER TRANSFORMER TESTING METHODS PROGRAMMABLE LOGIC PROGRAMMABLE LOGIC CONTROLLER Parallel Port EXPANDER Paschen's law Piezoelectric Wave-Propagation Transducers Potential Transformer RADIO INTERFERENCE RECTIFIERS REGULATION OF ALTERNATOR REGULATION OF THREE PHASE ALTERNATOR Read a Capacitor SINGLY-EXCITED SOLIDS AND LIQUIDS Classical gas laws Secondary effects Semiconductor strain gages Speaker Driver Strain Gages Streamer theory Superposition Superposition theorem Swinburne’s Test TMOD TRANSFORMER TESTING METHODS Tape Recorder Three-Phase Wattmeter Transformer Tap Changer Transformer Testing Vector group test Virus Activity Voltage Insulator Coating Voltage To Frequency Converter Voltage to current converter What is analog-to-digital conversion Windows work for Nokia capacitor labels excitation current test magnetic balance voltage to frequency converter wiki electronic frequency converter testing voltage with a multimeter 50 hz voltages voltmeter

Search More Posts

Followers