Computer-based methods for determining the head of a linked list

• US 5,446,889 A
• Filed: 07/21/1994
• Issued: 08/29/1995
• Est. Priority Date: 07/21/1994
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Kogen, Clark C., Prestifilippo, James
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): WANG, PETER
• Application Number:
  US08/278,179
• Time in Patent Office: 404 Days
• Field of Search: 395/600, 395/700
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A computer-based method for identifying the head of a linked list stored in a memory comprises the steps of (a) retrieving an element of the list from the memory, (b) identifying from the pointer of the retrieved element, the next subsequent stored element of the list, (c) marking the next subsequent stored element; and (d) repeating steps (a) through (c) for each stored element of the list. After processing each element, the stored element that is not marked is identified as the head of the linked list. In an alternate embodiment, an element of the list is selected as a possible candidate for head of the list, and the list is then traversed from the selected element to the end of the list. A count of the number of linkages between the selected element and the end of list is generated as the list is traversed, and each element accessed while traversing the list is marked "visited". Each other element of the list is then processed in the same manner, except that elements already visited are not processed. Additionally, if while traversing the linkages from a candidate element to the end of the list, an element is encountered that was previously "visited", then the linkage count associated with the previously visited element is added to the linkage count generated up until that point for the candidate element. Upon completion, the element with the largest linkage count is identified as the head of the list.

Claims

1. A computer system comprising:

a processing unit;

a memory connected to the processing unit;

a linked list comprising a plurality of elements each stored at a different location in said memory, each stored element of the linked list comprising information and a pointer that points to a next subsequent stored element in the linked list,

the processing unit being programmed to;

a) retrieve one of the stored elements of the linked list from said memory;

b) identify, from the pointer of said retrieved element, the next subsequent stored element of the linked list;

c) mark said next subsequent stored element;

d) repeat steps (a) through (c) for each other stored element of the list; and

thereafter,

e) identify which of said stored elements is not marked, and designate the stored element that is not marked as a head of the linked list,

whereby the processing unit is able to identify the head of the linked list when such information has been lost or is inaccessible.

2. The computer system of claim 1 wherein said linked list comprises a queue of processes to be executed by the processing unit, each stored element comprising information related to one of the processes in the queue.

3. The computer system of claim 1 wherein said processing unit is further programmed to maintain an array having a plurality of elements equal to the number of stored elements of said linked list, each element of said array corresponding to a respective one of the stored elements of said linked list.

4. The computer system of claim 3 wherein the processing unit is programmed to mark said next subsequent stored element by setting the corresponding element of said array to a pre-defined value indicative of said marking.

5. The computer system of claim 4 wherein the processing unit is programmed to identify which of the stored elements is not marked by identifying the element of said array that is not set to said pre-defined value.

6. The computer system of claim 1 wherein the linked list stored in said memory comprises a singularly linked list.

7. A computer system comprising:

a processing unit;

a memory connected to the processing unit;

a linked list comprising a plurality of elements each stored at a different location in said memory, each stored element of the linked list comprising information and a pointer that points to a next subsequent stored element in the linked list,

the processing unit being programmed to;

a) select one of said stored elements from said memory;

b) traverse successive linkages of the list from the selected element to the end of the list, mark each stored element accessed during said traversal including the selected element, and generate, for the selected element, a linkage count representing the number of linkages traversed from the selected element to the end of the list;

c) repeat steps (a) and (b) for each of the other stored elements of the list, but only if said other stored element was not marked during a previous traversal of the list; and

d) identify the stored element for which a largest linkage count was generated, and designate the identified element as a head of the linked list,

whereby the processing unit is able to identify the head of the linked list when such information has been lost or is inaccessible.

8. The computer system recited in claim 7 wherein if during traversal of the list from a selected element to the end of the list, an element is reached that was marked during a previous traversal of the list, the processing unit is further programmed to terminate the traversal of the list for the selected element and to add the linkage count of the marked element to the linkage count generated for the selected element prior to reaching the marked element.

9. The computer system recited in claim 7 wherein said linked list comprises a singularly linked list.

10. The computer system recited in claim 7 wherein said linked list represents a queue of processes to be executed by the processing unit, each stored element containing information related to one of the processes in the queue.